Prove a^4n b^m is irregular using puming lemma My assignment is to prove that the language

$L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language.

My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an equal #a and #b if you "pump down" your $v$ so that it is $v^0$, so that the condition $n > m$ is no longer fulfilled. Then I realized I completely disregarded that it's $4n$ and not just $n$, so I wasted a lot of time on that.

Now I'm absolutely out of ideas, because as I see it you can always find an number $p$, so that you can pump a number of as however often you want as long as p is divisible by 4 because if you divide your word $z = uvw$, both $u$ and $v$ need to have a number of as divisible by 4 as to not break the $4n$ condition.

However, that would mean that you absolutely can not prove that $L$ is not regular using the pumping Lemma, which contradicts the assignment. Where is the flaw in my logic?

I would really appreciate some pointers.

Yes, you can use the pumping lemma. It looks like your line of thoughts just had a minor glitch.

Suppose your adversary claims the pumping lemma for $L$ works for some number $p\ge1$.
You can pick $z=a^{4(p+1)}b^p$, a word that "barely" satisfies the requirement.
Your adversary claims $z=uvw$ where $|v|\ge1$, $|uv|\le p$ and for all $n\geq 0$, $uv^{n}w\in L$.

Since $|uv|\le p<4(p+1)$ and $z$ starts with $4(p+1)$ consecutive $a$'s, there must be no $b$ in $uv$. That is, $v=a^i$ for some $i=|v|\ge1$.

Consider $uv^0w=uw$. Since $z$ "barely" satisfies the requirement, removing some $a$'s without removing any $b$ will make $z$ not satisfying the requirement. You have beaten your adversary, again.

The above proof works, in fact, for any language $M$ such that $L\subseteq M\subseteq \{w\mid \#_a(w)\ge4(\#_b(w)+1)\}$.

I have been saying "$z$ 'barely' satisfies the requirement", since it is easier to understand that way although it is not very rigorous. It should be quite easy for readers to make it rigorous.


Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton Is there any general result to show that which automaton is more succinct? I have a set of LTL properties and I would like to know (show) which automaton is more efficient in term of state number and edge number.

Consider a nondeterministic Büchi automaton $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, \alpha\rangle$. The acceptance condition of $\mathcal{A}$ is a subset of states $\alpha\subseteq Q$, and an infinite run $r = q_0, q_1, q_2, \ldots$ over an infinite word $\sigma_1\sigma_2\cdots $ is accepting iff $r$ visits a state in $\alpha$ infinitely many times.
In Rabin automata, the acceptance condition is given by $\alpha = \{\langle \alpha_1, \beta_1 \rangle, \langle \alpha_2, \beta_2 \rangle, \ldots , \langle \alpha_k, \beta_k \rangle \}$, where $ \alpha_i, \beta_i\subseteq Q$, for all $i\in [k]$. An infinite run $r = q_0, q_1, q_2, \ldots$ over an infinite word $\sigma_1\sigma_2\cdots $ is accepting iff for some $i\in [k]$, $r$ visits a state in $\alpha_i$ infinitely many times, and visits the states in $\beta_i$ finitely many times. The number $k$ is the index of the automaton, and is usually taken into account when defining the automaton's size.
Clearly, a Büchi condition $\alpha$ is equivalent to the Rabin condition $\{ \langle \alpha, \emptyset \rangle\}$. Thus, nondeterministic Büchi automata can be translated to nondeterministic Rabin automata with no blowup (they can be thought of as a simple fragment of Rabin automata - although they are equally expressive).
So, nondeterministic Büchi automata cannot be more succinct than nondeterministic Rabin automata. However, a nondeterministic Rabin automaton with $n$ states, $m$ transitions, and index $k$, can be translated to a nondeterministic Büchi automaton with $O(n\cdot k)$ states, and $O(k\cdot m)$ transitions. The later translation is justified by a lower bound. So, nondeterministic Rabin automata are polynomially more succinct than nondeterministic Büchi automata, which is not significant.
A comprehensive overview of the translations can be found here (along with other relevant references).
Note that you can easily translate an LTL formula into a nondeterministic Büchi automaton (see section 6 here), and the translation has a tight exponential bound. However, following your comment, if you're interested in translating the LTL-formula into a deterministic automaton, then you can translate the Büchi automaton to a deterministic Rabin automaton (such determinization construction has a tight bound of $2^{\Theta(n \log n)}$). Also, the double exponential blow-up of translating LTL formulas to deterministic automata cannot be avoided (see theorem 26 here).


Boolean algebraic expression vs Propositional logic expression There is a lot of similarity between Propositional logic and Boolean algebraic expressions.

Similar aspects :

1) Both has variables of two states.

2) Operations of Boolean algebra and propositional logic are similar.

3) Simplification of formula expressed in logic can be minimized using Boolean algebra and vice versa.

My doubt is are they both same? If same, why studying differently? I mean why can't Propositional logic can be directly applied to digital logic instead of introducing Boolean algebra again(academically)?

They are not the same, but I don't blame you for thinking that they are. The reason why it doesn't seem clear that they are the same is that you've only seen one example of each.

So let's step back, define them separately, and then look at some interesting examples.

Propositional logic is a branch of mathematics that studies propositions, their truth or falsity, and how they combine.

What you probably think of as "propositional logic" is actually just one kind of propositional logic, namely, classical logic. However, this is not the only kind of classical logic, and not the only one that is interesting in computer science.

Some theories are built on top of classical logic. Presburger arithmetic, for example, is the theory of natural numbers with addition. Tarski arithmetic is the theory of real closed fields. First-order logic is the theory of quantified variables over non-logical objects.

You can think of these logic systems as types of propositional logic, with more axioms to deal with the extra stuff. Many constraint-type problems are expressible in this framework; you can look up satisfiability modulo theories for more information on how this is used.

But there are also propositional logics which are not "classical". One example of a non-classical logic is intuitionistic logic. This is a logic which models constructive proofs, which is interesting, because constructive proofs are the same thing as well-behaved computer programs. ("Well-behaved" in this sense means there is no unbounded recursion.) They are also the basis for modern type systems, such as that of Haskell.

Constructive proofs (e.g. pick any proof from Euclid's Elements) are implementable as computer programs. Given some geometric objects as input, you could implement the proof (at least in principle) as a computer program which performs the construction.

You can't do that with non-constructive proofs. Let's look as an example to see what I mean. I'll prove that there are two irrational numbers, $a$ and $b$, such that $a^b$ is rational.

Consider $z = \sqrt{2}^\sqrt{2}$. This number is either rational or irrational.

Case 1: If $z$ is rational, then set $a = b = \sqrt{2}$, and the theorem is proven.

Case 2: If $z$ is irrational, set $a = z$ and $b = \sqrt{2}$. Then $a^b = 2$ and the theorem is proven.

QED

The reason why this proof isn't constructive is that it relies on the law of the excluded middle; $z$ must be either rational or irrational, but we don't (and, in a sense, can't) actually test which of them is true.

Intuitionistic logic systems tend to give you proof systems which are decidable. This is an extremely important practical concern. If you consider, for example, the Java bytecode verifier, or the type system for a programming language (both of which prove that some program is type-correct), they must terminate with an answer, so they must be based on a decidable proof system. By allowing propositions which are neither provable nor refutable, you avoid Gödel-like incompleteness.

That's just one example, of course. Other non-classical propositional logics include modal logics (which can be used to model situations where you have multiple agents who know different things; think about network protocols), and temporal logics (where the truth or falsity of a proposition may change over time).

The thing that connects all of them is the notion of a "proposition". Propositional logic can be thought of as the study of a family of logic systems, all of which deal with the notion of a mathematical statement which has a "truth"-type judgment.

Boolean algebra, on the other hand, is a purely algebraic system, characterised by a set of axioms. Saying "Boolean algebra" is like saying "group" or "field" in abstract algebra. Classical propositional logic satisfies the axioms, but so do other mathematical structures.

The subsets of a set $S$, for example, form a Boolean algebra; with the "not" operator corresponding to "set complement", "and" corresponding to "set intersection", and "or" corresponding to "set union". You can think of "true" as being $S$ and "false" being the empty set, but these are not the only "truth values" which the system models.

Lattices form Boolean algebras, and some lattices are important in computer science (e.g. Scott domains). Moreover, some important non-classical logic-like systems naturally form Boolean algebras, such as fuzzy logic.

So what I hope you can see is that while the two notions are related (some Boolean algebras model some propositional logics), they are not exactly the same thing. How they differ is part of what makes them interesting.


On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972) I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" want to prove that the average height $h_n$ of a tree with $n$ nodes (that is, the maximum number of nodes from the root to a leaf) satisfies $h_n \sim \sqrt{\pi n}$.

The outline is as follows. Let $A_{nh}$ be the number of trees with height less than or equal to $h$ (with the convention $A_{nh} = A_{nn}$ for all $h \geqslant n$) and $B_{nh}$ the number of trees of $n$ nodes with height greater than or equal to $h+1$ (that is, $B_{nh} = A_{nn} - A_{nh}$). Then $h_n = S_n/A_{nn}$, where $S_n$ is the finite sum
$$
S_n = \sum_{h \geqslant 1} h(A_{nh} - A_{n,h-1}) = \sum_{h \geqslant 1} h(B_{n,h-1} - B_{nh}) = \sum_{h \geqslant 0} B_{nh}.
$$
It is well known that $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, for the set of general trees with $n$ nodes is in bijection with the set of binary trees with $n-1$ nodes, counted by the Catalan numbers.

Therefore, the first step is to find $B_{nh}$ and then the main term in the asymptotic expansion of $S_n$.

At this point the authors use analytical combinatorics (three pages) to derive
$$
B_{n+1,h-1} = \sum_{k \geqslant 1} \left[\binom{2n}{n+1-kh} - 2\binom{2n}{n-kh} + \binom{2n}{n-1-kh}\right].
$$

  My own attempt is as follows. I consider the bijection between trees with $n$ nodes
  and monotonic paths on a square grid $(n-1) \times (n-1)$ from $(0,0)$ to $(n-1,n-1)$ which do not cross the diagonal (and are made of two kinds of steps: $\uparrow$ and $\rightarrow$). These paths are sometimes called Dyck paths or excursions. I can express now $B_{nh}$ in terms of lattice paths: it is the number of Dyck paths of length 2(n-1) and height greater than or equal to $h$. (Note: a tree of height $h$ is in bijection with a Dyck path of height $h-1$.)

  Without loss of generality, I assume that they start with $\uparrow$ (hence stay above the diagonal). For each path, I consider the first step crossing the line $y = x + h - 1$, if any. From the point above, all the way back to the origin, I change $\uparrow$ into $\rightarrow$ and vice versa (this is a reflection wrt the line $y=x+h$). It becomes apparent that the paths I want to count ($B_{nh}$) are in bijection with the monotonic paths from $(-h,h)$ to $(n-1,n-1)$ which avoid the boundaries $y=x+2h+1$ and $y=x-1$. (See figure.)

In the classic book Lattice Path Counting and Applications by Mohanty (1979, page 6) the formula
$$
\sum_{k \in \mathbb{Z}} \left[\binom{m+n}{m-k(t+s)} - \binom{m+n}{n+k(t+s)+t}\right],
$$
counts the number of monotonic paths in a lattice from $(0,0)$ to $(m,n)$, which avoid the boundaries $y = x - t$ and $y = x + s$, with $t > 0$ and $s > 0$. (This result was first established by Russian statisticians in the 50s.) Therefore, by considering a new origin at $(-h,h)$, we satisfy the conditions of the formula: $s=1$, $t=2h+1$ and the destination point (the upper right corner) is now $(n+h-1,n-h-1)$. Then
$$
B_{nh} = \sum_{k \in \mathbb{Z}} \left[\binom{2n-2}{n+h-1-k(2h+2)} - \binom{2n-2}{n-h-1+k(2h+2) + 2h+1}\right].
$$
This can be simplified in
$$
B_{n+1,h-1} = \sum_{k \in \mathbb{Z}} \left[\binom{2n}{n+1-(2k+1)h} - \binom{2n}{n-(2k+1)h}\right],
$$
which, in turn, is equivalent to
$$
B_{n+1,h-1} = \sum_{k \geqslant 0} \left[\binom{2n}{n+1-(2k+1)h} - 2\binom{2n}{n-(2k+1)h} + \binom{2n}{n-1-(2k+1)h}\right].
$$
The difference with the expected formula is that I sum over the odd numbers ($2k+1$), instead of all positive integers ($k$).

Any idea where the problem is?

The monotonic paths from $(−h,h)$ to $(n−1,n−1)$ that you construct only avoid the boundary $y=x+2h+1$ before they cross $y=x+h$ for the first time. Thus the formula you use is not applicable.


C++ Strings vs. Character Arrays Why do you think it is that most C++ instructors teaching college level computer sciences discourage or even forbid using strings for text, instead requiring students to use character arrays?

I am assuming this methodology is somehow intended to teach good programming habits, but in my experience I don't see anything wrong with just using strings, and they are significantly easier to use and learn.

Koenig and Moe's Accelerated C++ and Stroustrup's Programming: Principles and Practice Using C++ are using std::string and other components from the standard library from the start. If I remember correctly, they don't even present C arrays for Koenig and Moe and Stroustrup does it quite late in the book (perhaps even just in an annex).

That approach, qualified as modern, is the preferred one in my circles.  The other approach, often qualified as historic, follows more closely how C++ evolved, but doesn't take advantage of "newer" (relatively, they are 15 years old now) development and doesn't teach what is practised now (at least on projects not encumbered with too much legacy) but 10 years ago (there is always a lag before being mainstream).


Can we show a language is not computably enumerable by showing there is no verifier for it? One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following:

  $A \subseteq \Sigma^*$ is c.e. iff there is a decidable language $V\subseteq \Sigma^*$ (called verifier) s.t.
  for all $x\in \Sigma^*$,

  $x\in A$ iff there exists a $y\in\Sigma^*$ s.t. $\langle x, y \rangle \in V$.

So one way to show that a language is not c.e. is to show that there is no decidable verifier $V$ for it. Is this method useful to show that languages are not c.e. in practice?

In practice, we don't usually prove just that a language is r.e. or not r.e.. If the language is r.e., we want to know whether it is recursive. If it is not r.e., we want to know what sort of Turing degree it has, not just that the Turing degree is not r.e..

For example, if $P$ is a problem with $P' \equiv_T 0'''$ then $P$ is not r.e., but that fact about the Turing jump is more informative than just knowing $P$ is not r.e.

So while, in principle, you could show that a language is not r.e. by proving there is no verifier, in practice it is more informative to prove that the language is not r.e. by showing that it computes something that no r.e. set can compute; the nature of that 'something" typically gives useful information about the problem being studied.


Running time for Testing Polygonal Neighbours for Intersection or Inclusion I was reading this  paper by Shamos, M.I, on "Geometric Intersection Problems" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.9983&rep=rep1&type=pdf) , and was trying to understand it's Theorem 6, which says " Whether any two of N convex k-gons intersect can be determined in O(N(k+log N log k)) time."

I was stucked on the point 3 (Inclusion and intersection tests), in which the author says that " When a polygon is inserted, it ,it must be tested against its immediate neighbors for inclusion or intersection. As we have seen before, each such test can be done in O(k) time. "

I do not understand how is that possible. Theorem 5 of the same  paper states that determining an intersection of two k-gons takes O(k log k) time.

If the author is talking about something else, then I didn't get that.
Any help appreciated.
Thanks.
Moon

In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with convex polygons, which are a special kind of simple polygons.

The 'As we have seen before, ...' refers to this line: 'As we have seen before, each such test can be done in $O(k)$ time.$^8$', where $8$ references another paper.

However, even though I do not know why you are reading this paper, I'd advise against it. This paper is pretty old and the main result (the $n\log n$ segment intersection algorithm) has been both improved upon and better explained by other sources. If you did not have an introductory course on computational geometry or something similar, I advise you to look at a computational geometry /algorithmic geometry textbook or lecture notes first.


Introductory books on nature sciences behind bioinformatics My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background in biology and chemistry to feel prepared for that cycle of lections (I was rather weak at these subjects at school).

Could you recommend any books that would provide a good introduction to the questions of natural sciences that bioinformatics focuses on?

As a previous response stated, it is not an absolute requirement that you study biology in order to do bioinformatics.  However, if you wish to have a background understanding of the foundational concepts such as genes, RNA, DNA, etc. then a good introductory biology book should provide everything that you need.

Molecular biology is not the kind of topic that one can simply dive into the middle of, though. Therefore, in order to understand it, you need to do some introductory reading.   The best book is one that has enough detail without assuming that you wish to become a biologist.

I suggest that you look at Collins Outline of College Biology. Reading chapters 2-5 and 12-15, should give you basic information you desire.  Another choice is Schaum's Outline of Biology, Third Edition, chapters 2-4 and 7-10.   Both books cost less than $20.00 and are easy to understand.  Hope this helps.


Why can L3 caches hold only shared blocks? In a recent CACM article [1], the authors present a way to improve scalability of shared  and coherent caches. The core ingredient is assuming the caches are inclusive, that is higher-level caches (e.g. L3, one global cache) contain all blocks which are stored in their descendant lower-level caches (e.g. L1, one cache per core).

Typically, higher-level caches are larger than their respective descendant caches together. For instance, some models of the Intel Core i7 series with four cores have an 8MB shared cache (L3) and 256KB private caches (L2), that is the shared cache can hold eight times as many blocks as the private caches in total.

This seems to suggest that whenever the shared cache has to evict a block (in order to load a new block) it can find a block that is shared with none of the private caches² (pigeon-hole principle). However, the authors write:

  [We] can potentially eliminate all recalls, but only if the associativity, or number of places in which a specific block may be cached, of the shared cache exceeds the aggregate associativity of the private caches. With sufficient associativity, [the shared cache] is guaranteed to find a nonshared block [...]. Without this worst-case associativity, a pathological cluster of misses could lead to a situation in which all blocks in a set of the shared cache are truly shared.

How is this possible, that is how can, say, 1MB cover 8MB? Clearly I miss some detail of how such cache hierarchies work. What does "associativity" mean here? "number of places in which a specific block may be cached" is not clear; I can only come up with the interpretation that a block can be stored multiple times in each cache, but that would make no sense at all. What would such a "pathological cluster of misses" look like?

Why On-Chip Cache Coherence is Here to Stay by M. M. K. Martin, M. D. Hill, D. J. Sorin  (2012)
Assuming the shared caches knows which blocks are shared where. This can be achieved by explicit eviction notifications and tracking bit, which is also discussed in [1].

Perhaps I can shed some light on associativity. These caches aren't just open blocks of memory, so don't think of them as some kind of generic container. Each block of memory has a real address (whether this is physical or virtual doesn't matter, just assume it is a fixed address). At each level of cache this memory can only be cached at very specific locations in the cache.

For example, memory address X can be stored in the L1 cache at location Y0. This is a direct mapping. But suppose it can also be stored at location Y1, then it is 2-way associative (which is fairly common). Being storable in N-locations makes it N-way associative. When the chip chooses a cache location it checks only these N places -- it does not scan the entire cache (which would be too slow/complicated).

This should clarify what they mean by saying the shared cache must have an aggregate higher associativity than the lower caches. So if L1 is 2-way, L2 is 4-way, and there are 4 processors, they shared cache must be > 24-way associative (I don't have the article, but this sounds like what they mean). This follows then, that at least one of these shared locations must not be cached in any of the private caches.

I can't say for sure what their "pathological" case is, but I can explain a common one, one that can affect things like binary search. Say the L1 cache is 1-way associative and 4KB in size. The locations where memory can be stored is likely a simple mod of the address (X mod 4K). Say then you have a large block of data which is a power of 2 (which is common). In a binary search you always chop the size in half, so a search on a 256K block would have you check address 128K, 64K, 32K, 16K, 8K, 4K, and the lower.  But you should see a problem here. Those first 6 addresses all map to the exact same cache location. So each access requires an eviction and load, despite you accessing only a tiny amount of memory.


Prove a network is a feedforward network if and only if the numbering of its cells satisfy these conditions Undergraduate math student here attempting to understand neural networks. Picked up a text on sale, "Neural Network Learning and Expert Systems" (Gallant), and I'm just starting on the exercises for chapter 1.

The full question is:

Prove that a network is a feedforward network if and only if its cells are numbered in a way such that:

all $p$ input cells are numbered from $1$ to $p$.
whenever cell $u_j$ is connected to cell $u_i$, then $j < i$.

The definition of a feedforward network, according to Gallant, is a directed network such that there are no cycles between any nodes.

I'm confused for a few reasons.

This sounds like I'll need at least a basic understanding of graph theory, which I don't have. Any quick and dirty resources that should cover what I need for this kind of material? I don't even know how to represent a network like this mathematically.
I'm used to the numbering of things being pretty arbitrary, for example, numbering basis vectors in a set just to differentiate between them. I don't really have an intuitive idea for why the numbering of input cells is a factor in deciding if a network has directed cycles or not.

Thanks in advance.

One direction (given such a numbering, there are no cycles) is elementary, and I encourage you to work it out on your own. The other direction is topological sorting.


Betweenness centrality measurement ignoring inverse paths? I'm implementing the Betweenness Centrality algorithm proposed by Brandes (first algorithm on this paper - also below), and I'm running into a very weird issue: it seems to be ignoring some paths (i.e. for vertexes v-w, it may count the path v-e-w, but not the inverted path w-e-v). I'm not sure how to prove or debug this issue, but I'm pretty certain that's what happening. The precise issue that I can see in the debugger is that two nodes that should have the same BC value are off by roughly three units. I'm using the double type to store the values.

Am I missing something about this algorithm? The graph I'm examining is unweighted and undirected btw.

Also, on a totally unrelated note: the value being computed on each step is the following:

Shouldn't the value be between 0 and 1?

Algorithm:

The algorithm that you have mentioned here is definitely correct. You can refer to the correctness proof in the paper.

This algorithm is implemented in many libraries and ready to be used including NetworkX, Boost, GraphStream, and MATLAB (3rd party I guess) and many others. Also, many other people (including myself) and companies have employed the same algorithm.

If you are getting unexpected results, please revise your implementation.


How many edges before a random graph is connected? Let $G$ be a undirected graph with $n$ vertices and no edges, and let $f(k)$ be the probability that if we add $k$ edges randomly to $G$ that $G$ will be connected. How would one determine $f(k)$ for a given $n\in\mathbb N$?

Specifics:

When we add an edge to the graph $G$, any edge that can exist would be equally likely to be added. We can not add the same edge twice, so when $k=\frac{n^2+n}2$ (the number of possible edges in a graph with $n$ verticies), then $f(k)=1$.

Definition for connected may be found on wikipedia.

A classical result of Erdős and Rényi states that if $k = \frac{n}{2} (\log n + c)$, then as $n\to\infty$, the probability that the graph is connected tends to $e^{-e^{-c}}$. You can find the proof in any textbook on random graphs.


aⁿbⁿcⁿdⁿ using 2-stack PDA I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$.

Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and $d$'s respectively won't work because that would mean number of $a$'s $= $number of $c$'s and number of $b$'s$ =$ number of $d$'s. I can't come up with an accurate solution.

Check out this link: https://stackoverflow.com/questions/40317006/pushdown-automaton-pda-for-l-anbncnn-1#= or check the answer below.

2 stack PDA to recognize the language {an bn cn dn n>=0} for this we should follow the given steps:

Use the first stack for checking an bn, this can be done by pushing a whenever you see an a and then popping a when you see a b.

Use the second stack for checking bn cn  this can be done by pushing b whenever you see a b and then popping b when you see a c.

Use the first stack for checking cn dn  this can be done by pushing c whenever you see a c and then popping c when you see a d.

Accept if both stacks are empty at the end of this process, otherwise do not accept it.

Let ^ and z be the stack symbol of stack 1 and 2 respectively, then the transition diagram of the above PDA will be as follows:


Importance of Frequency vs CAS Latency in memory performance I was looking at the Wikipedia page for CAS Latency: https://en.wikipedia.org/wiki/CAS_latency

And I noticed the obvious trend - at higher frequency, despite CAS latency degrading (growing), the delay to get the 1st, 4th and 8th word overall improved regardless.

I've heard in the past that frequency/CAS was perhaps the best metric for memory performance as a consumer, but this chart seems to disagree:

So my main question(s) are:

Is getting the 1st, 4th and 8th word an accurate representation of real-world performance of memory? If not, why not, and what would be?
If there some other factor to memory performance that would be a third "hidden variable" that I'm not accounting for, that's not constant between all these? The IMC's performance at high frequency? The motherboard's? Signal noise?

Thanks for any thoughts!

The presented timing for first word assumes the row is currently open (i.e., is only CAS latency, in nanoseconds). For random accesses, RAS latency is added; if another row in the bank is still active, PRECHARGE latency (to write back the active row before opening the desired row) is added. RAS and PRECHARGE latencies are typically proportional to CAS latency.

Given that cache misses add both cache probing delay and various delays in the on-chip network (including queuing delay) and at the memory controller (e.g., scheduling delay), the delay of the DRAM chip itself are a little less significant. (Adding buffering to support larger capacity, e.g., load-reduced DIMMs, further increases latency.)

(There are additional constraints on DRAM activity, so some access patterns may be unexpectedly slow compared to the simple model of PRECHARGE, RAS, CAS.)

Frequency controls peak bandwidth, which is more important for some workloads. Frequency also determines the occupancy of a DRAM data channel, so a higher frequency DRAM can satisfy more requests per second as long as they are "well-behaved" (only accessing different rows in the same bank will be slow), reducing queuing delays.


What is postorder traversal on this simple tree? Given the following tree:

Which traversal method would give as result the following output: CDBEA?

The answer in my study guide is Postorder, but I think postorder would output: DEBCA. Am I wrong?

You are not wrong.

A postorder  traversal visits the left subtree, then the right subtree, then the root of the current tree (recursively).


Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'? Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as:

$h_1(n)$ = number of misplaced tiles
$h_2(n)$ = total Manhatten distance

Could anyone tell why $h_2$ is a better heuristic than $h_1$? I would like to know why the number of nodes generated for $h_1$ is greater than that for $h2$. Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

Source: Informed Search

There probably will be no formal proof; probably the only way to tell which is better is through experiments.

But some intuition seems possible.  $h_1$ only takes into account whether a tile is misplaced or not, but it doesn't take into account how far away that tile is from being correct: a tile that is 1 square away from its ultimate destination is treated the same as a tile that is far away from where it belongs.

In contrast, $h_2$ does take this information into account.  Instead of treating each tile as either "correct" or "incorrect" (a binary decision), $h_2$ introduces shades of grey that take into account how far the tile is from where it belongs.  It seems plausible that this might possibly yield some improvement.

Of course, the only way to find out which one actually works better is to try the experiment.  But this might give some intuition about why one might reasonably hope that $h2$ could be potentially be better than $h_1$.


“Fuzzy” Chinese Remainder Theorem NP-hard? I have some "fuzzy" congruences like these:
\begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&\equiv a_3 \mod 7 \text{ with } a_3 \in \{1,2,6\}\\ \end{align}
These example moduli would provide a unique solution for $x \bmod lcm(3,5,7)$, if the $a_i$ were fixed.
Because the $a_i$ are not fixed, these "fuzzy" congruences lead to $2*3*2=12$ possible solutions for $x \bmod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, I'm also given an additional constraint $x < B$, which provides an upper bound for $x$.

We can assume that all moduli $m_i$ are primes, so $lcm(m_1,m_2,...,m_n) = \prod_i m_i$.
Furthermore each $a_i$ has at most $t$ possible values ($t=3$ in the upper example).

So the general problem is that we are given a constant $t$, primes $m_1,\dots,m_n$, an upper bound $B$, and sets $U_1,\dots,U_m$ (each of size at most $t$), and the goal is to find an integer $x$ such that $x \bmod m_i \in U_i$ for all $i$ and $0 \le x < B$.

Is this problem NP-hard and how can I prove this?

This question is related to another one: "Fuzzy" Chinese Remainder Theorem, but the difference is that here the sets $U_i$ can be arbitrary and need not contain consecutive integers.

My initial approach was to use the k-Vertex-Cover problem for the reduction.
I used the Wikipedia Integer programming NP-hardness proof as a template (https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness).

Let $G=(V,E)$ be an undirected graph. Define a linear program as follows:
\begin{align}
\sum_{v \in V} y_v \leq k&  \\ y_v+y_u \geq 1 && \forall uv \in E \\ y_v \geq 0 && \forall v \in V
\end{align}

I tried to define the Vertices as $a_i$.

But I am unable to transform the $y_v+y_u \geq 1 \text{ , } \forall uv \in E$ (set contains at least one vertex of each edge) inequalities into "fuzzy" congruences.

If you allow arbitrary modulus (so $m_i$ is not required to be prime), your problem is NP-hard.  In particular, it is NP-hard to determine whether there exists any valid solution, even without the upper bound $B$.

To prove this, we can reduce 3SAT to the problem.  Suppose we have a 3SAT formula $\varphi$ over variables $v_1,\dots,v_n$.  Let $p_1,\dots,p_n$ be the first $n$ primes.  Then we will associate one congruence per clause of $\varphi$.  In particular, the clause $v_i \lor v_j \lor v_k$ corresponds to the congruence

$$x \equiv a \pmod{p_i p_j p_k} \text{ where } a \in U$$

and $U=\{c_{001},c_{010},c_{011},\dots,c_{111}\}$ contains seven values, where $c_{def}$ is the unique constant such that $c_{def} \equiv d \pmod{p_i}$, $c_{def} \equiv e \pmod{p_j}$, and $c_{def} \equiv f \pmod{p_k}$.  Do the same for each other clause; e.g., for $v_i \lor v_j \lor \neg v_k$, the set $U$ has the seven values $U=\{c_{000}, c_{010}, c_{011}, c_{100}, c_{101}, c_{110}, c_{111}\}$, and so on.

In this way, we obtain a system of congruences with one congruence per clause of $\varphi$.  We don't need an upper bound on $x$ (you can use the trivial upper bound $x < p_1 p_2 \cdots p_n$ if you like).  Then there exists a solution to this system of congruences iff the formula $\varphi$ is satisfiable. In particular, a satisfying assignment $(v_1,\dots,v_n)$ for $\varphi$ corresponds to a unique value for $x$ that satisfies all the congruences, namely, the value such that $x \equiv v_i \pmod{p_i}$ for all $i$.

This reduction does require the ability to choose moduluses that are not prime.  I don't know if the problem becomes any easier when every modulus is prime.


NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA? I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are unconcerned here with whether the states are accepting), then the problem of "deciding whether there exists some $N$-state DFA for which each $s_i$ causes that DFA to end up in state $q_i$" is NP-complete.
A much more well-known result by Gold (1978) is the same as the above, except with the alphabet being arbitrary instead of binary, and the examples being in the form $(s_i, \mathrm{accept})$ and $(s_j, \mathrm{reject})$ instead of having the state $q_i$. That result is discussed in some other threads, like this, this, and this.
If I naively try to reduce from the Gold problem to the Sipser problem, I would try to replace all "accept" with a single "terminal" accept state, and same for reject, but that fails because if you wanted only a single terminal accept state to handle all accepted strings, you would need to have an NFA with epsilon transitions; if you try to convert that back to DFA, the single terminal states may split up into multiple, which would invalidate your examples.
I suspect Myhill-Nerode may be useful here, since the DFA states correspond to the equivalence classes of strings. I think you can rephrase the Sipser result as deciding whether some given set of strings can be partitioned into some given set of Myhill-Nerode equivalence classes.
I searched through the literature, but was not able to find the Sipser result anywhere. What is another decision problem that we can use as a polynomial-time reduction here? Alternatively, is this result derived or discussed anywhere else?

(Note: the below proof may have some issues raised in the comments. I am in the processing of addressing the issues.)
The following "end-character" method was suggested in the comment above, as well as private communication with some others. Any mistakes are my own.
We construct a polynomial-time reduction from the Gold problem (arbitrary alphabet with "accept" or "reject" in the examples) to the Sipser problem (binary alphabet with states in the examples). Since the Gold problem is NP-complete, it then follows that the Sipser problem is also NP-complete.
The Gold decision problem gives us an integer $n$ and pairs $(s_1, x_1), (s_2, x_2) \ldots (s_k, x_k)$ [where each $s_i$ is a string in some arbitrary alphabet $\Sigma$, and each $x_i$ is either "accept" or "reject"] and asks if there exists an $n$-state DFA $G$ that for each $i$, accepts or rejects $s_i$ based on the value of $x_i$.
We claim that the Gold input has such an $n$-state DFA if and only if the examples $(t_1, y_1) \ldots (t_k, y_k)$ has a corresponding $f(n)$-state DFA $H^\prime$ in the Sipser problem, where:

$t_i$ is some binary encoding of $s_i$ plus a common suffix $Z$ that is unambiguously different from any of the other encoded characters in $\Sigma$.
$y_i = q_{x_i}$; that is, either $q_\mathrm{accept}$ or $q_\mathrm{reject}$
$f(n)$ is a function that be computed and written down in time polynomial in $\log n$.

First, suppose the Gold DFA $G$ exists. Then, there exists a size $O(n \log \lvert \Sigma \rvert)$ DFA $H$ that recognizes the homomorphism ($\Sigma$ encoded into binary) of the language of $G$: simply take every transition in $G$ and split up into transitions corresponding to the binary encoding. Since $G$ may have more than one accept state, so does $H$ (which has the same number of accept states as $G$). Hence, modify $H$ by taking every accept state and inserting transitions corresponding to the "end of string" bitstring $Z$ to a single newly-created $q_\mathrm{accept}$, and inserting the same transitions from non-accept states in $H$ to a single newly-created $q_\mathrm{reject}$. The resulting DFA $H^\prime$ clearly fits the examples $(t_i, y_i)$, and its number of states is bounded above by some easily computed $f(n)$.
Now for the other direction, suppose some $f(n)$-state DFA $H^\prime$ exists which fits the examples $(t_i, y_i)$. Then, since by construction every $t_i$ has the "end of string" bitstring $Z$ as a suffix, we simply take $H^\prime$ and for every state $q$ for which reading $Z$ would take $H^\prime$ to $q_\mathrm{accept}$, we make $q$ an accept state. Then, we remove $q_\mathrm{accept}$ and $q_\mathrm{reject}$, and we have the DFA $H$. We can then construct a DFA $G$ which recognizes the same language with characters decoded from binary to alphabet $\Sigma$. This construction can easily be done by starting with the start state in $G$, trying out every encoded character in $\Sigma$ and writing down the transitions in $G$, and recursively repeating. Since $H$ is finite, this procedure is guaranteed to terminate in polynomial time.
(Note: the above solution simply quotes the Gold result, the proof of which is pretty involved. There's probably a simpler method that directly proves the Sipser result instead of using Gold as an intermediary.)


Removing edges of a weighted graph I have an edge weighted $N{\times}N$ graph and the edge similarity values are bound to $[0,1]$. What I am trying to do is to find a cut-off threshold below which I can say that that edges are noisy/ non relevant. What I have tried so far is  removing edge values that are below median or 60% - 70% quantile. Another approach I have tried is to generate random graphs and calculate random edge similarity as $ randSim = \frac{\#edges\_drawn}{\#edges\_sampled}$  and remove edges with vales <= random similarity.
The issue I am facing is that the first approach is too arbitrary and very few edges are removed using the second approach. Do you have suggestions for other edge pruning approaches ?

Thank you.

Your current approaches are very ad hoc, so they don't sound promising.  Instead, I think you're going to need some domain knowledge.  I suggest you start by characterizing the process by which the graph was generated.  First, try to develop a probabilistic model that describes the distribution on such graphs (absent noise).  Then, develop a probabilistic noise that describes the noise.

Suppose $X$ is a random variable that represents the original graph, and $Y$ is the random graph after adding noise to $X$.  You observe the value of $Y$, say $y$.  Now your goal is to estimate $X$.  So, this becomes a probabilistic inference problem. One approach will be to use maximum likelihood methods: find the value $x$ that maximizes $p(x|y)$ (where $p(x|y) = \Pr[X=x|Y=y]$).  To do this, you'll need to know the probability distribution $p(x)$ on $X$ and the probability distribution $p(y|x)$ on $Y$ (conditioned on $X$); then you can use Bayes rule and find the $x$ that maximizes the likelihood value $p(x|y)$ by noting that

$$\begin{align*}
p(x|y) &= p(y|x) p(x)/p(y)\\
&= {p(y|x) p(x) \over \sum_{x'} p(y|x') p(x')}.\end{align*}$$

Since $y$ is fixed, the denominator is a constant (it does not depend on $x$).  Therefore, maximizing $p(x|y)$ is equivalent to maximizing $p(y|x) p(x)$.  So, once you have a probabilistic model for $X$ and $Y$ and know the distributions $p(x)$ and $p(y|x)$, you can then try to infer the original noiseless graph by finding the value $x$ that maximizes $p(y|x) p(x)$.


Is logical address generated by CPU and MMU same if Physical and Virtual address space are same? The system has same physical and virtual address space i.e. 32-bit. Are the logical address generated by CPU and address generated by MMU same?

It can be but not necessarily.

The MMU can be setup to translate adresses. There is nothing stopping you from having swapping physical adresses between, say, two logical segments and still have the same amount of logical and physical adresses. Sounds a bit unusual to me, but not impossible.


Depth First Search to find Minimum spanning tree A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example of a graph where a DFS won't find the minimum spanning tree regardless of how the adjacency list is ordered. Is this correct or not? I can't come up with a counter example and intuitively it seems correct...

No you wont. Suppose you have as graph the complete graph $K_n$ with $n\ge 4$, for simplicity we pick the $K_4$, but this construction works for all larger $n$.

Every DFS-tree of a complete graph is a path, no matter how you order the edges. But clearly you can define the weights such that a non-path is the MST. See the example below (MST in red).


Find binary number with max hamming distance wrt given set of binary numbers Suppose we have a set $A$ of binary numbers with the same length $n$.
For example (with $n=8$):

$A = \{ 10010011, 01011011, 00010010, 11110001\}$

Now, I want to find the binary number $z$ (also with $n$ bits) such that the minimum hamming distance between $z$ and any of these numbers is maximized.

i.e. $z = \arg \max \{ d(x,A) \mid x \in X\}$

with

$d(x,A) := \min \{ d(x,a) \mid a \in A\}$

where $X$ is the set of all $n$-bit binary numbers, and $d(x,a)$ the hamming distance between $x$ and $a$.

Is there any efficient algorithm for this?

Obviously, if $n$ is small enough we can brute-force this, but I'm looking for something more efficient when $n$ is large. The size of $A$, on the other hand, can be assumed relatively small, so any algorithm polynomial in $|A|$ is fine. Also, it does not have to be an exact algorithm. Any algorithm that approximates the correct answer is welcome too.

Here is the decision version of the problem, which we can the problem of farthest string.

  Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s_i)\ge k$ for all $i$.

There is the problem of closest string.

  Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s_i)\le k$ for all $i$.

Farthest string is dual to closest string.

Let $c$ denote the map that changes a binary string to its 1's complement, i.e., switching 0 and 1 everywhere. For example, $c(010010111)=101101000$. Note that $c\circ c = Id$.

Given an instance of farthest string $(m, n, s_1, s_2, \cdots, s_m, k, s)$, we can construct an instance of closest string $(m, n, c(s_1), c(s_2), \cdots, c(s_m), n-k, s)$. Call this transformation of instances $r$.

For every string $s$ of length $n$, $$d(s,s_i)+d(s, c(s_i))=n.$$
Hence
$$d(s,s_i)\ge k\text{ for all }i\  \Longleftrightarrow\ d(s,c(s_i))\le n-k\text{ for all }i. $$

So $r$ converts a yes-instance of farthest string to a yes-instance of closest string. Symmetrically, $r$ converts a yes-instance of closest string to a yes-instance of furthest string. Furthermore, $r\circ r= Id$.

So $r$ is a linear duality reduction between farthest string and closest string.

All results about closest string are about farthest string.

That is because of the duality reduction. Now we can dive into the Wikipedia article on closest string to see find what we have about closest string.

In particular, we know that farthest string is NP-complete. We can check approximability, fixed-parameter tractability as well.


DP recurrence relations: Coin change vs Knapsack Take:

KP recurrence relation

$ max { [v  + f(k-1,g-w ), f(k-1,g)] } $    if w <= g and k>0

CCP recurrence relation

$ min {[1  + f(r,c-v), f(r-1,c)]} $      if v <= c and r>0

I don't understand (much as I've researched) exactly what the reasoning is behind KP comparing in both cases (take the element/don't take it) to the above row $('k-1')$ while CCP only does this when it doesn't take the coin (the same number that's a row above in the same column persists).

To evaluate the case where the coin is taken, CCP says to go back on the same row as much columns as you get when subtracting the coin value of that row from the column you're in . Then it says to add 1 (because you'd be taking the coin).

Supposing I understood this well enough, the latter logic makes perfect sense to me. I don't see the need for KP to go up a row when taking the element (I see why it adds 'v' and goes back a number of columns, it's just the $'k-1'$ that baffles me)

What's the logic behind this?

_

EDIT:

Underlined in red you'll find what I'm referring to, more especifically.

  Knapsack 0-1 Problem:

Take the 24 : it's the result of comparing the 15 directly above it (not taking the element) to the 15 up and to the left (taking the element) . This last 15 is not on the same row as 24 is.

See source: http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf

  Coin Change Problem:

Goes back on the same row where our starting point is(case where coin is taken).

See source: (page 2): http://condor.depaul.edu/rjohnson/algorithm/coins.pdf

The knapsack problem only allows you to add each item once.  Subtracting from $k$ is, in a sense, iterating through the items and resolving a different one each recursion.

Put another way, if you didn't subtract 1 from $k$, you'd be able to add the same element multiple times.


Can every Turing Machine be translated into a SAT formula? For the proof of "Cook-Levin Theorem", for a Turing Machine $M$ that accepts a language $L \in NP$ and input $x \in \{0,1\}^*$, we can create a SAT Formula,  that is satisfiable if and only if $M$ accepts $x$. Could we adopt this construction so that for any Turing Machine $M$ and input $x \in \{0,1\}^*$ we can create a SAT Formula $\phi$ that is satisfiable if and only if $M$ accepts $x$ (even if this SAT Formula has more than polynomial length of $|M|$)? Or would that contradicts Rice's Theorem?

Edit: As dkaeae correctly pointed out, defining a SAT formula that is satisfiable iff a TM $M$ accepts an input $x$ is indeed possible. What I meant to ask though is, whether a reduction in the sense of a computable function exists (albeit not being limited to running in polynomial time, but indeed being somehow limited in the running time).

The proof of the Cook-Levin theorem shows that for any nondeterministic Turing machine $M$, any input $x$, and any (reasonable) time bound $t(n)$, we can construct (efficiently) a SAT formula of size proportional to $t(|x|)^2$ that is satisfiable iff $M$ accepts $x$ within $t(|x|)$ steps.

If you know that $M$ is supposed to halt within $t(n)$ steps, then the SAT formula captures the behavior of $M$ on $x$. But for a general Turing machine we don't possess any a priori bound on the running time. This is why you cannot solve the halting problem in this way.


I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs Add a constant $c\geq |w_{min}|$ to each edge of $G$, so that each edge now has non-negative weight.
Run Dijkstra's algorithm

Can anyone tell me if this is viable or if it fails?

I'm afraid that this idea does not work (and I actually post this question as homework to my students, the reason being that at first glance it looks sound and complete).

Let $G(V, E)$ denote a graph with a cost function $c:e\in E\mapsto Z$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $e\langle v_i, v_j\rangle$ with a negative cost, i.e., $c(e_{ij}) <0$, so that $w_{min}=c(e_{ij})$.

Let $G'(V, E)$ denote a graph where the cost of each edge is now $c'(e_{ij})=c(e_{ij}) + w_{min}, \forall v_i, v_j\in V$. Certainly, there are no negative edge costs in $G'$.

Running Dijkstra on $G'$ to find the shortest path between two arbitrary vertices $s$ and $t$ would return a path $\pi:\langle s=v_0, v_1, v_2, ..., v_n=t\rangle$ with a cost equal to $\sum_{i=0}^{n-1}c'(e_{i, i+1})=\sum_{i=0}^{n-1}\left(c(e_{i,i+1})+w_{min}\right)=n\times w_{min}+\left(\sum_{i=0}^{n-1}c(e_{i, i+1})\right)$ ---please note the usage of $c'$ and $c$ in these expressions. In other words, the overall cost of paths in $G'$ penalizes larger paths by the constant $w_{min}$ and in the end, it might very easily return a different path.

It does not matter whether you correct now the cost of the path returned by running Dijkstra in $G'$, as it might be simply different.

Hope this helps,


BST representation of Hash Tables I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables.

I googled a lot for BST Representation of Hash Table. Code in C++ but didn't find any link or example. Can someone help me with the implementation. I'm really confused how to represend Key-Value pairs on BST. And what if there are collisions etc.

All, I found was comparison b/w BST and HasTables:

https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree
https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/

What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications

The node of the BST would have  the following structure. $Node \space := (Key,Value)$.
Insert a key-value pair by performing comparisons on the keys of two different pairs.
Avoids nodes with redundant keys  i.e. before insertion, if a node in the BST with the same key value exists, do not insert it. Else if no node with the same key exists, insert the key-value pair.
No change in delete function.
Search returns $null$ if no node's key matches, else return the value associated with the key which was searched.

Then use these  functions assuming that these perform the corresponding operations on a HashTable.
Using a self-balancing BST would give $O(log\space n)$  time complexity for all the three functions defined above. And iterating through all the key-value pairs would simply mean doing an in-order traversal of the BST.


Relational algebra and indexes How might indexes be represented in the context of relational algebra?

How would an optimizer transform a query to use indexes?

Indices must not appear in relational algebra. That is because relational algebra is just a formal language which describes what you must do, but not how you must do it.

It is comparable to the multiplication and other operations of the elementary arithmetic.
There is a definition of what multiplying is but not of the way how you have to do it. There are several algorithms to multiply two numbers but the results are all equal. For further information see Wikipedia (What does it mean to multiply two natural numbers?).

Relating to your question that means that the result of an operation is the same with or without indices. The only difference is the increasing performance if you use indices.


Maximize vertex cover weights with bounded edge weights in a connected subgraph Similar questions were asked elsewhere, but no satisfying answers occurred yet.

In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is bounded and the sum of internal vertex weights is maximum. Is this problem NP-hard? Please note that the subgraph has to be connected, and the sum of internal edge weights is calculated by the weight of Minimal Spanning Tree of this subgraph. An example is shown in  attached.

Attention: previously someone suggested that we can set the bound to 0 to reduce the problem to Maximum Independent Set. However, by setting all the bound to 0, the problem should be reduced to finding the node with maximum weight, for the nodes in the independent set are not connected which would cost infinite cost.

This is already NP-hard in the special case that the graph is a tree, since Knapsack can be reduced to such an instance of this problem: Let $v_i$ be the value of the $i$-th item, and $w_i$ its weight.  Create a vertex of weight $v_i$ for each item $i$, and a single extra vertex that is connected by an edge of weight $w_i$ to each item $i$.  A capacity-$b$ knapsack can be filled with items of value at least $k$ iff the solution to the constructed instance of your problem with total edge capacity $b$ can achieve a total vertex-value of $k$.


Under what circumstances are one-way functions reducible to their hard-core bits? I've seen competing claims about hard-core predicates. On the one hand, there's the basic definition

  Let $f : \{0,1\}^n \rightarrow \{0,1\}^k$ and $b : \{0,1\}^n \rightarrow \{0,1\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$,
  $$
\mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\,.
$$

But I've also read the statement

  We want the problem of finding $x$ to be reducible, in polynomial time, to the problem of finding $b(x)$, so that finding $b(x)$ is just as hard as finding all of $x$. In that case $b$ is called a hard-core bit for $f$.

How are these requirements related? Is one stronger than the other? Or do they imply each other?

Inverting a one way function is not always reducible to evaluating a hardcore bit. As an example, consider trivial hardcore predicates. Let $f$ be one way and define $g(x,b)=f(x)$ where $b\in\{0,1\}$. Obviously $b$ (the rightmost bit of a string) is a hardcore predicate for $g$, however knowing it does not bring you any closer to finding the rest of the string. The problem is that such predicates are probably of no use. Usually, we cant afford to lose information (e.g. while constructing pseudorandom generators), so we won't be able to base hardcore predicates on a part of the input that we're not using.

To overcome the above problem (i.e. ignoring trivial hardcore predicates), we can demand that evaluating the predicate will help us reverse the function (if this is the case, then $f(x)$ and $h(x)$ cannot be independent). The generic construction in Goldreich-Levin's theorem indeed yields such a predicate. If $f$ is one way and $g(x,r)=(f(x),r)$, then an algorithm computing $h(x,r)=\langle x,r\rangle$ can be used to find $x$ (just feed it $f(x)$ along with different values of $r$).


Pushdown automaton for complement of { ww | ... } I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams).

So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL.
I also read somewhere that any odd word is part of $L'$ (what about even length words?). So a pushdown automaton description could be: read one letter and put into stack, then read next letter and remove previous letter from stack. Do this until the end. If one letter is left in the stack at the end then word is odd length thus accept, else reject?

You write

  So, I already know that $L = \{ww \mid w \in (0,1)*\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL

Indeed $L'$ is context-free, but your argumentation is ...eeuh... nonsense. Shure, CFL are not closed under complement, meaning there exist context-free languages of which the complement is not context-free. In general however the complement of a CFL can be both CFL or non-CFL. Even if the complement of every CFL would be non-CFL [which is NOT the case] it would NOT follow that the complement of every non-CFL is CFL.

The language $L'$ indeed consists of all strings of odd length (that is a regular language and can be checked without using the stack) plus the strings of even length for which both halves differ. For the latter part see here.

Phrased more explicitly, let $K = \{ xy \mid |x|=|y|, x\neq y \}$ be the language from question 307 linked above. My claim is that $L' = K \cup \{ x \mid |x| \text{ is odd } \}$, as $L$ equals $\{ xy \mid |x|=|y|, x= y \}$. (And so this explains, as you say in your question, why odd and even length strings are treated separately.)

To answer your question how to implement this using a PDA, see the problem I have linked and its answers. A little hint. To check a word is of the form $xy$ with $|x|=|y|$, but $x\neq y$ we must be able to write $x=x_1ax_2$ and $y=y_1by_2$ with $a\neq b$, and both $|x_1|=|y_1|$ and $|x_2|=|y_2|$. Unfortunately we cannot check both length requirements at the same time. We can however test whether $|x_1y_2|= |x_2y_1|$, and that is enough. Essentially we find the matching positions of $a$ and $b$ without expicitly finding the middle of the string. (This is not at all obvious, please make some drawings.)


Space complexity below $\log\log$ Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$.

It's well known fact in Space Complexity, but how to show it explicitly?

So here is the main idea behind this fact. Let us denote by $C$ all possible configuration of the $l(n)$-space bounded TM. Notice that $|C|\le 2^{c\cdot l(n)}$, where $c$ is a constant depending on $M$.

We assume that the input tape is a two-way tape. Let $w$ be a word of size $n$, such that for all smaller words $u$ we have $l(w)>l(u)$. When the head moves from position $i$ to position $i+1$ on the input tape, or vice versa, we record the current configuration of the computation in the crossing sequence $C_i$. Assume we have $i\neq j$ with $C_i=C_j$. Then we define as $w'$ the word obtained from $w$ by deleting everything between the characters number $i$ and $j$. We observe that $w'$ is a shorter word which uses the same amount of space. Contradiction, there is no such $w$.

If $l(n)\in o(\log\log n)$ then you have $o(\log n)$ configurations and $o(n)$ crossing sequences. Hence two crossing sequences are the same.

Notice that if your input tape is 1-way, then even with $o(\log n)$ space you are doomed.


If I walk through list and delete every out-of-order element I come across, on average how many elements will be left? I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list). What I'm left with is a shorter list that's guaranteed to be in-order.

Example: The starred elements of this list would be deleted during the walk through.

[1, 4, 2*, 3*, 5, 7, 6*] -> [1, 4, 5, 7]

My question is: On average, what will be the length of the remaining list? And is there some simple/obvious form of the distribution of this?

And as one follow-up: if we used this for a sorting algorithm (called Drop Sort), what would the run-time be? To be clear, the algorithm would be something like this:
$$\textit{DropSort}(\text{list}) = \textit{Merge}(\text{Remaining list}, \textit{DropSort}(\text{Rejected list}))$$

This question was inspired by this r/ProgrammerHumor post.

You can compute the average using linearity of expectation.

Let the random variable $X$ denote the number of elements that are retained.  Let $X_i$ be an indicator r.v. that is 1 if the $i$th element is retained, or 0 otherwise.   Then $X = X_1+\dots + X_n$, so

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$

Now the $i$th element is retained if and only if it is the largest number among the first $i$ elements in the list.  Therefore, $\Pr[X_i=1]=\frac{1}{i}$, so

$$\mathbb{E}[X] = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \approx \log(n) + \gamma$$

In other words, the average length of the remaining list is $O(\log n)$.

I don't know what the distribution is.

As a heuristic, the expected running time of Drop Sort would satisfy a recurrence something like $T(n) \approx T(n-\log(n)) + O(n)$, which corresponds to $O\left(\frac{n^2}{\log n}\right)$ time.


How to convert 2 or gates (x1 V x2 V x3) to NAND How can I convert a clause of size 3 that is made of 2 OR gates

example:

(x1 OR x2 OR x3 )

to one or more clauses of size 4 made only of NAND gates and not gates? So without parentheses inside the clauses.

examples:

(x1 NAND x2 NAND x3 NAND x4)
(not x1 NAND x2 NAND not x3 NAND not x4) AND (x1 NAND x2 NAND x3 NAND x4)

additional notes:
The original question asked is to prove that 4-SATCNF (A CNF expression that can be satisfied, with clauses of size 4 and with NAND gates between the 4 terms.) is NP-Complete by showing the polynomial reduction of 3-SAT <=p 4-SATCNF. I'm stuck at the part where I need to find a function for the reduction. I suppose the function should be something around the form showed above, if not can somebody helped me find the good function?

Thank You

Articles that I consulted so far:

3-Sat to 4-sat polynomial conversion: https://www.csie.ntu.edu.tw/~lyuu/complexity/2012/20121106s.pdf

NAND Conversion:
https://en.wikipedia.org/wiki/NAND_logic

(x1 or x2 or x3) = (not x1 NAND not x2 NAND True NAND not x3)


Grover's Algorithm result when the desired element is not present What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?

When it is absent, it will just output one arbitrary state.

As it is not the desired element, you may repeat the search algorithm again (even in the case it was present, you could have measured another computational basis – the algorithm uses probability after all so that's why it may be necessary to repeat) and you will finally conclude that it is not present.

The inversion about average operator changes the amplitudes of the states $\alpha_i$ to
$$ - \alpha_i + 2 \langle\alpha\rangle\,, $$
where the last term is the average of the amplitudes. You see in the case of no marking, it has no effect, so all computational bases will have the same probability of being measured.

You can check the explanation in Nielsen and Chuang's book.


Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values:
a, b, c, d ⊆ ℝ
i ⊆ {true, false}

// unconditional inequality constraints
a < b

// conditional inequality constraints
i -> b < c
i -> b < d
!i -> b > c
!i -> a < d

and I would like to answer questions about the system, such as "is a greater than d?" and "is c less than d?".
One approach would be to formulate this as an integer linear program: in the example above, the non-indicator variables would have domains [0, 3], the indicator variables [0, 1] and a feasible solution might be:
i = 0 (false)
a = 0
b = 1
c = 0
d = 2

I could then answer "is a greater than d?" by comparing the integer values assigned to a and d.
However, I could get the wrong answer for "is c less than d?": the solution above suggests yes, but there exists another feasible solution
i = 0 (false)
a = 0
b = 3
c = 2
d = 1

in which the answer appears to be no. (The correct answer is that we cannot determine the relationship between c and d.)
Now, I could generate ALL the feasible solutions, iterate over them, and check whether c < d in each one -- but I have to answer enough of these questions that this approach would be too slow.
Is there a more efficient and elegant way? Perhaps constraint programming is not even the right way to think about this -- I considered formulating it as a directed graph-search problem instead, where directed edges represent inequality relationships, but my actual system contains conditional constraints as well. The wonderful answer that I received on a related question (https://scicomp.stackexchange.com/questions/36090/constraint-programming-problem-with-conditional-constraints-and-some-unknown-ind) directed me here. Glad for any suggestions or references to relevant papers or textbooks!
Edit: After asking this question to several people (both here and elsewhere), I have received multiple suggestions to reduce these constraints to a comparability graph. To illustrate the challenges of this approach, I have added conditional constraints to my example system above. Is there a way to incorporate such constraints into a comparability graph?

If the constraints you have are of the form $a < b$ and $a=b$ (i.e., only unconditional inequality constraints), you can model them with a directed graph: each node represents a variable, and an edge $v \to w$ corresponds to the inequality $v < w$.  Then you can answer queries by doing a straightforward reachability check.  (If you see the equality $v=w$, then merge the two vertices $v,w$ into a single vertex.)

When you add conditional equality constraints, the problem becomes NP-hard.
Proof of NP-hardness: I will show a reduction from 3SAT to your problem.  Suppose we have a 3SAT formula $\varphi$ on variables $x_1,\dots,x_n$.  Consider a single $C_i = \ell_i \lor \ell_j \lor \ell_k$, where $\ell_i,\ell_j,\ell_k$ are three literals (e.g., $\ell_i$ is either $x_i$ or $\neg x_i$, etc.).  We will translate this to the constraints
$$\begin{align*}
\ell_i \implies &y_{i0} > y_{i1}\\
\neg \ell_i \implies &y_{i0} < y_{i1}\\
\ell_j \implies &y_{i1} > y_{i2}\\
\neg \ell_j \implies &y_{i1} < y_{i2}\\
\ell_k \implies &y_{i2} > y_{i3}\\
\neg \ell_k \implies &y_{i2} < y_{i3}\\
\end{align*}$$
$$y_{i0} > y_{i3}$$
Notice that if at least one of $\ell_i,\ell_j,\ell_k$ are true, then these seven constraints are simultaneously satisfiable; but if $\ell_i,\ell_j,\ell_k$ are all false, then they are not satisfiable.  So, we translate each clause of $\varphi$ into several constraints as above, obtaining a large system of constraints.  Then this system has a satisfiable solution if and only if $\varphi$ is satisfiable.
In conclusion, testing satisfiability of your kind of constraints is NP-hard.  It follows that answering queries is also NP-hard (answering a query is the same as testing satisfiability of the constraints plus the query).  Consequently, you shouldn't expect any algorithm that is both efficient and always correct.
If you have to solve it in practice, you could try applying a SAT solver.  Add boolean variables $s_{b,c}$ to represent $b<c$; then you can translate each constraint into a clause.  For instance, $b<c$ translates into $s_{b,c}$, and $i \implies b<c$ translates into $\neg i \lor s_{b,c}$.  Finally, add clauses that enforce the consistency of the $s$'s, i.e., $\neg s_{a,b} \lor \neg s_{b,c} \lor s_{a,c}$ for each $a,b,c$.  Now answering a query amounts to conjoining the query and testing satisfiability of the resulting SAT formula, which you could do with an off-the-shelf SAT solver.  Some SAT solver allow you to "push" a clause, test satisfiability, and then "pop" the clause.


Are there functions in the same Θ-class that are not linear transformations of each other? looking for some help, or at least if I'm going the right direction...

  Are there functions $f$ and $g$ such that $f$ is $O(g)$ and $g$ is $O(f)$ and NO constants $c_1$ and $c_2$ exist for which $f(x) = c_1 \cdot g(x) + c_2$?

I want to say that there is not, because the definition of big O states that if $f(x)$ is $O(g(x))$ then $|f(x)| \leq c_1 \cdot |g(x)|$ for all values $x > k$

and if $f(x) = c_1 \cdot g(x) + c_2$ then $g(x) = \frac{f(x) - c_2}{c_1}$

and thus $0 \leq f(x) \leq c_1 \cdot g(x)$

$0 \leq c_1 \cdot g(x) + c_2 \leq c_1 \frac{f(x) - c_2}{c_1}$

$0 \leq c_1 \cdot g(x) + c_2 \leq f(x) - c_2$

$0 \leq c_1 \cdot g(x) \leq f(x)$

Which contradicts the initial definition of $f(x)$ being $O(g(x))$.

Am I on the right path, here?

Your proof must be wrong since the result is incorrect. For example, if $f=x^2$ and $g=x^2+x$ then $f = \Theta(g)$ but $f$ is not an affine shift of $g$. To see where the proof goes wrong, I suggest substituting these $f$ and $g$ in the proof and seeing which step fails. This is how one debugs their proof.


Is "Feral Concurrency Control" a disparaging description? The paper Feral Concurrency Control:
An Empirical Investigation of Modern Application Integrity uses the term "feral" in a way I have never seen before.

  Rails has developed a range of concurrency control strategies,
  two of which operate external to the database, at the application
  level, which we term feral concurrency control mechanisms.

The paper shows that various application-level data validations are less reliable than database-level checks.

The only usage of "feral" I'd seen previously applied to untamed animals - eg, "feral cats".

Are the authors using the term disparagingly, or does "feral" mean something different in this context?

Sorry for coming to this issue so late. For context, I am one of the coauthors of the paper. The term "feral concurrency control" in the paper was inspired by the common usage "feral database" (similarly "feral system") said by IT admin people, to refer to databases or systems that were run by staff outside the control of IT services. For example, a university department might keep a database of student information, separate from the centrally managed official student record system. See https://en.wikipedia.org/wiki/Feral_information_systems

The connotation is of something that has escaped from control and is acting wild (like a feral cat is a cat that is, or descends from one which, escaped from domestication and became wild)


Curiosity on system device nomenclature - Gaussian Mixture Models Would not know if this is the best SE website to ask, but I could not find anything better, especially because the answer might involve a fair amount of computer science (although this is an hypothesis).

I hold a MSc. in Statistics, and thus have extensively explored Gaussian Mixture Models. That's why, upon buying my brand new Lenovo E580 laptop (Windows 10 Pro x64), I was surprised to find, under the System devices drop down menu in the Device Manager, a reference to GMMs (although I'm not sure what the actual item is pointing to). I have included a picture to clarify the point.

Questions

1) What is the highlighted item referring to?

2) How do GMMs have anything to do with this?

These are accelerators for Gaussian Mixture Modelling used for speech recognition and video processing applications.  They can be typically accessed via openCL libraries.

GMMs are used for efficient classification of partial or noisy data e.g. speaker voices or people object in videos.


Does the empty language have a CFG in CNF? I just not sure does empty set have a context-free grammar in Chomsky normal form?

That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal form. I am not sure. Can some one explain?

Note that every context-free language has a grammar in CNF (that is proven) and $\emptyset$ is context-free, so the answer is clearly: yes!

Do you get from $S \to S$ to it, using the normal transformation algorithm? No, because the usual algorithm requires a reduced, chain-rule free grammar as input; yours does not fit.

Approach one: use the algorithms (from lecture or textbook) to remove the chain rule, and try again!

Approach two: start with another grammar that fulfills the criteria!

   Approach two is doomed to fail for most grammars: in order for a grammar to derive not a single word, it can not have any rules that are not thrown out by reducing.

 Thus, the only (kind of grammar) that works is $(\{S\}, \Sigma, \emptyset, S)$, that is a grammar with no rules at all. Note that it is in CNF.


Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic) I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? Mathematical or dynamic programming?

Objective:

I have a set of 48 classes with 25 students each. I need to divide each class in two groups, lets call them A and B. There are the following constrains:

Some students have brothers/sisters in other classes. I need that all brother/sister be in the same partition A or B. This
should be a hard condition that must be fulfilled by the solution.
A second constrain is that girls and boys should be equally divided in the both partitions of each class. If class 12 has 11 boys and 14 girls; the partition should be: partition 12A with 6 boys and 12 girls and partition 12B with 5 boys and 12 girls. This constrain is not hard, it may be violated by the solution slightly.

What if the number of constrains increases a lot.

In the comments, it is suggested to use a greedy algorithm, because it is easy to move students with no constrains (no siblings) from one partition to another.
What to do if the number of constrains is very high. For some reason we have a lot of constrains of the type: studentA can't be in the same partition of studentB, ... What algorithmic approach is best?

Some numbers:

There are around 1200 students, divided in 16 years. Each year has 3 classes. The ratio girls and boys is, as expected, 1:1.
There should be between 500 and 600 brother/sister relations.

Background:

Due to the COVID19 pandemic it is possible that next school year, students may be separated in two groups. These groups will alternate going to school and staying at home. To easy the logistics for parents, it may be desirable to have all siblings in the same group, going to school or staying at home.

The very general problem is (weakly) NP-complete if you want the optimal solution, however, in general there aren't arbitrarily large sibling cliques.

The problem can always be modeled as an integer linear program (ILP).

If you just want a good enough solution, then I would start with a greedy algorithm, followed by local search.  You can always keep the local search (with random restarts) running over the night in hope for ever better solutions.

Since you seem to have added some more constraints in comments, if the constraints are really hard constraints, you can consider using an off-the-shelf ILP solver.

For illustrative purposes, I picked the first I could (cvxpy) find in a programming language I am familiar with (Python).  I am not familiar with ILP solvers, so I have no idea if this is a good choice.  (Note that it is not actually a solver, but an interface for several solvers.)

So I wrote a short example just to get you started.  It can be done in about 50 lines.

There are $2 \cdot N$ variables:

$N$ variables representing the $N$ students
$N$ variables representing their genders (linked through a constraint)

There are two constraints:

siblings need to be in the same partition
a helper-constraint to make the balancing of genders simpler

The optimization is basically to optimize (minimize)

$$2 \cdot (N/2 - \sum{s})^2 + (N/2 - \sum{g})^2,$$

where $\sum{s}$ is the number of students put in partition 0 and $\sum{g}$ is the number of girls put in partition 0.

caveat emptor

from collections import namedtuple, Counter
import random
import cvxpy as cp

Student = namedtuple("Student", "name level gender")

def generate_students(N=100):
    # generate random data
    students = [Student(i, 1, random.choice("MF")) for i in range(N)]

    siblings = []
    for i in range(0, N // 2, 3):
        siblings += [(i, i + 1), (i, i + 2), (i + 1, i + 2)]
    return students, siblings

def create_variables(students):
    """Return stud_var and gender_var.

    These will be constrained to be set to the same value, i.e.

    stud[i] == gender[i].

    This is to ensure that we can easily count gender-difference in
    addition to "normal" difference.

    """

    stud_vars = [cp.Variable(1, boolean=True) for s in students]
    gender_vars = [cp.Variable(1, boolean=True) for s in students]
    return stud_vars, gender_vars

def create_constraints(stud_vars, gend_vars, students, siblings):
    stud_const = [stud_vars[l] == stud_vars[r] for (l, r) in siblings]
    link = [stud_vars[i] == gend_vars[i] for i in range(len(stud_vars))]
    return stud_const

def create_objective(stud_vars, gend_vars):
    mid = len(stud_vars) // 2
    objective = cp.Minimize(
        2 * (mid - cp.sum(stud_vars)) ** 2 + (mid - cp.sum(gend_vars)) ** 2
    )
    return objective

students, siblings = generate_students()
stud_vars, gender_vars = create_variables(students)
constraints = create_constraints(stud_vars, gender_vars, students, siblings)
objective = create_objective(stud_vars, gender_vars)
prob = cp.Problem(objective, constraints)

result = prob.solve()
if result is None:
    exit("Could not find feasible solution.")

print(round(result))
print(Counter(int(round(e.value[0])) for e in stud_vars))

def get_gender_count(partition):
    lst = [
        students[idx].gender
        for (idx, s) in enumerate(stud_vars)
        if round(s.value[0]) == partition
    ]
    return Counter(lst)

print("Partition 0:", get_gender_count(0))
print("Partition 1:", get_gender_count(1))

# for idx, e in enumerate(stud_vars):
#    print(students[idx], "\tPartition", int(round(e.value[0])))

for (l, r) in siblings:
    lv = int(round(stud_vars[l].value[0]))
    rv = int(round(stud_vars[r].value[0]))
    assert lv == rv

Running the snippet output:

(e375) [ubuntu ~/textnik]$ time python textnik.py
297.0
Counter({0: 52, 1: 48})
Partition 0: Counter({'F': 27, 'M': 25})
Partition 1: Counter({'F': 25, 'M': 23})

real    0m4,060s
user    0m4,926s
sys 0m1,189s

meaning that it put 52 students in one group and 48 in the other, with 27/25 F/M in the first group and 25/23 F/M in the other group.

All the siblings should be in the same group by constraints.


What problem cannot be solved by a short program? BACKGROUND:

Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of the $n!=6$ orderings of the 3 numbers. I.e., there is one solution for the case $A>B>C$, another solution for $A>C>B$, etc. (the case $A>C=B$ can be solved by any one of these two solutions).

Thinking of the case $n=4$, it seems that the only way is, again, to consider all $n!=24$ different orderings and develop a different solution for each case. While the solution in each particular case is fast, the program itself would be very large. So the runtime complexity of the problem is small, but the "development time" complexity or the "program size" complexity is very large.

This prompted me to try and prove that my problem cannot be solved by a short program. So I looked for references for similar proofs.

The first concept that I found is Kolmogorov complexity; however, the information I found about this topic is very general and includes mostly existence results.

QUESTION:

Can you describe a specific, real-life problem $P$, such that any program solving $P$ on an input array of size $n$ must have a size of at least $\Omega(f(n))$, where $f(n)$ is some increasing function of $n$?

Since the answer obviously depends on the selection of programming language, assume that we program in Java, or in a Turing machine - whichever is more comfortable for you.

Every undecidable problem trivially satisfies this requirement because it has no solution at all. So I am looking for a decidable language.

For any given problem, you can create a programming language where a program to encode the solution to that problem is a single character. (cf. HQ9+). Kolmogorov complexity is language dependent. The answer to your question about which problems cause a blowup will depend heavily upon whichever "standard formal language" you choose.

There are some interesting results, however. Encoding of randomly generated strings will always require a cost proportional to the size of the string. Pigeonhole principle tells us there will always be some functions, in any fixed language L, that cannot be expressed in a space smaller than a complete enumeration of all the cases. And Blum's size theorem tells us that, for a total language, there are always functions you can encode larger than an arbitrarily chosen blowup factor compared encoding the same function in a Turing complete language.


Find the sum of the first K subsets of integer array We have given a multiset of $N$ integer, both positive or negative. Consider  all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ sums.

The problem is that $N$ can be very big number (up to 100000), so we cannot generate all subsets. How to optimize the search so we wont generate more than $K$ subsets.

$K$ in the problem will also be up to 100000.

I was thinking to get the smallest possible subset and then try to make it bigger and bigger, but I couldn't come to something that will work in all cases.

The problem is from past csacademy contest:
https://csacademy.com/contest/round-79/task/smallest-subsets/

Say the multiset is $S=M\cup P$ where $M$ is the set of negative numbers and $P$ is the set of non-negative numbers. Define $S^+=(-M)\cup P$ where $-M$ means the set of opposite numbers of elements of $M$. For a subset $T=(-M_T)\cup P_T$ of $S^+$ where $M_T\subseteq M$ and $P_T\subseteq P$, define $f(T)=(M\backslash M_T)\cup P_T$, which is a subset of $S$. Now easy to see $f$ is a bijection, and the sum of $f(T)$ is the sum of $T$ plus a constant (the sum of $M$). So we only need solve the problem on $S^+$, and transform the result, say $T_1,T_2,\ldots, T_K$ to $f(T_1),f(T_2),\ldots, f(T_K)$. That is to say, we only need to solve the problem where all elements are non-negative.

This is solved in this post. For completeness of this answer, I quote it here.

  (Going to assume nonempty subsets for simplicity. Handling the empty subset is a line or two.)

  Given a nonempty subset of indices S, define the children of S to be S \ {max(S)} U {max(S) + 1} and S U {max(S) + 1}. Starting with {1}, the child relation forms a tree that includes every nonempty subset of positive integers.

{1}
|  \
{2} {1,2}______
|  \     \     \
{3} {2,3} {1,3} {1,2,3}

  Keyed by the sum of corresponding array elements, this tree is a min-heap. If you compute the keys carefully (by adding and subtracting rather than summing from scratch) and implement the min-heap deletion lazily, then you get an O(k log k)-time algorithm.


Graph with repeated/redundant edges? Is a graph with two of the same edges a graph?
Specifically, can this graph be considered a directed graph?

Graphs, as usually defined, don't have parallel edges. Graphs with parallel edges are known as multigraphs.

However, like humpty dumpty, we can give a term whatever meaning we want. In some contexts, all graphs are multigraphs, and so the word graph denotes a multigraph. In other contexts, there are graphs and graphs with parallel edges. In yet other contexts, there are graphs and multigraphs. Only you know the conventions in your field.


Is a partial function Turing-computable? From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and various other sources I've read).

But then doesn't this mean that all partial functions are not Turing-computable? (and by extension not computable at all regardless of computational model due to the Church–Turing thesis?)

But this seems rather silly given that most real-world functions are partial, and many clearly computable...

This confuses me greatly, any help would be appreciated.

A) Is termination part of the definition of Turing-computability? (and computability in general)

B) How does non-termination fit into the concept of computability?

So, some of the functions you talk about might be technically uncomputable, but the problem can become decidable with trivial modifications.

For example, consider the function taking a natural number to its predecessor. If you define it partially, nothing comes before $0$, and there's no algorithm to solve this, because there isn't a correct answer. The algorithm can't find it because it doesn't exist.

But, if you make a choice, and say that the predecessor of $0$ is $0$, or some special character, now you have a total function, from which you can extract your partial one.

I suspect most of the "real world" partial functions you talk about fall into this category. You just define a special "fail" output for any inputs where there's no defined output.

What the definition of computability is talking about really is whether a Turing Machine halts for all inputs. If it halts on all inputs, the result is whatever is on the tape, so it's considered total. If it doesn't, then it's partial.

For your specific questions:

Yes, termination is absolutely part of the definition of computability. Otherwise, everything is decidable: I make a Turing machine that runs forever, and since it doesn't ever give a wrong answer, I've "solved" the problem. Given this, solving a problem without termination is pretty meaningless.

A function is computable if there exists a Turing Machine computing it which halts on all inputs.

How does non-termination fit in? Basically, we don't allow non-termination, because of the problem I mentioned above. There is a special class of problems, called "recursively-enumerable" or "semi-decidable" decision (yes/no) problems, where the Turing Machine halts on all "YES"-valued inputs, but might not halt on all NO-valued inputs.

Another thing to watch here is your quantifiers. A problem is decidable if there exists a Turing Machine that solves it and always halts. I can make a Turing Machine solving addition that sometimes loops forever, but that doesn't mean that addition is undecidable, because there exists another machine that solves it and always halts.


Find shortest path that visits all nodes in a given set of nodes Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice.

For example, consider the following:

I have attempted to solve this by first performing a breadth-first search to find the shortest path from A to B, then from B to C, and so on, taking care to exclude any paths already found at each iteration.

This greedy solution works for most inputs, but in some case it will fail to find a solution, as the shortest path between two target nodes may end up blocking the complete path.

Aside from a brute-force approach, is it possible to find the shortest path that visits all of the target nodes, and is guaranteed to find such a path if one exists? Any suggestions on how to proceed?

I answered a more general problem a couple days ago. You simply want the destination pairs to be (a, b), (b, c), (c,d ),etc.

The gist is to translate the problem into a minimum-cost integer multi-commodity flow problem with a maximum capacity of $1$ per node, and one commodity between each pair of destinations.


Are the following loops $O(n^2)$ complexity I'm presented with two snippets of code, and I need to determine their time complexity. I'm pretty convinced that both of these are $O(n^2)$, but I'm not 100% sure

1.)

2.)

It's quite easy, you just have to write down the first terms :

1.) The print instruction will be called $n$ times, then $n/2$ times, then $n/4$ times, etc...
Finally, the number of calls to print is $\Sigma_{i=0}^{\log n} \frac{n}{2^i} = n \Sigma_{i=0}^{\log n} \frac{1}{2^i} = n \frac{1-1/2^{\log n}}{1-1/2}=\mathcal{O}(n)$.

2.) The print instruction will be called $n$ times, then $n/2$ times, then $n/3$ times, etc...
Finally, the number of calls is $\Sigma_{i=1}^{n} \frac{n}{i} = n \Sigma_{i=0}^n \frac{1}{i} = \mathcal{O}(n \log n)$.


Any proof of correctness of the Toom-Cook algorithm? I found the toom-cook algorithm here: http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00037/Multiplication_1_print.pdf

and have been trying to chase down proof of it being correct, but can't find anything. Does anyone know how to go about proving the algorithm? I was thinking induction but I can't even figure out how to do it.

This is just for the three-way splitting, page 6. Any ideas?

If you're only interested in the three-way splitting…

We know that any natural number is a linear combination of powers of ten, where the coefficients are in the range [0,9]. This is our writing system for numbers: the coefficients are simply the digits of the number.

Let's assume that our number has at least six digits (just for simplicity). If it has less than that, we don't need Toom-Cook: $n$ is bounded by a constant, so we can do the multiplication in $O(1)$.

So our number can now be written as $a_0 10^0 + a_1 10^1 + a_2 10^2 + \cdots + a_n 10^n$, where all $a_i$ are single-digit non-negative integers. And $n$ is at least 6.

We also know that we can find $p$ such that $|(n - 2p) - p| \leq 1$. (If $n$ is divisible by 3, then $p = \frac{n}{3}$. If $n-1$ is divisible by 3, then we let $(n-2p)$ be larger by 1. And if $n-2$ is divisible by 3, then we increase $p$ by 1.)

Now, through the laws of multiplication and exponents, it's clear that our number is equal to $(a_0 10^0 + a_1 10^1 + \cdots) + (a_p 10^0 + a_{p+1} 10^1 + \cdots) 10^p + (a_{2p} 10^0 + a_{2p+1} 10^1 + \cdots) 10^{2p}$.

Thus, the number can be divided into three generally-close-to-equal parts, as the paper says.


Why shuffling by picking random position in all array instead of a part is not correct There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a random position. So for each element in an array I can generate a random position and put it there by swapping:

for (let i = 0; i < a.length; i++) {
    const position = rand.nextInt(a.length);
    const tmp = a[i];
    a[i] = a[position];
    a[position] = tmp;
}

This is almost what the improved Fisher–Yates shuffle algorithm is doing. However my solution is not correct. According to the link I need to generate numbers from the 0..i range, not from 0..length. Can anyone please explain me why it is so?

In my implementation all the numbers are still put into random positions, so what's the problem?

Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$. Therefore your algorithm could work only if $n^n/n!$ is an integer, which is only the case when $n \leq 2$.

More concretely, if you shuffle the array $1,2,3$, then you get the following results:
$$
\begin{array}{c|c}
\text{array} & \text{probability} \\\hline
1,2,3 & 4/27 \\
1,3,2 & 5/27 \\
2,1,3 & 5/27 \\
2,3,1 & 5/27 \\
3,1,2 & 4/27 \\
3,2,1 & 4/27
\end{array}
$$


Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential? This is probably a very basic question but one that I am having trouble finding a definitive answer for since this kind of thing is skimmed over in most introductory algorithms courses. Take an algorithm like DFS that runs in time polynomial in the number of inputs. In this case your input is a graph with $n$ vertices and $m$ edges, and your algorithm runs in time $O(m + n)$.

But we know that in reality we must always consider the lengths of binary encodings when calculating runtime. This is why something like the dynamic programming algorithm for Knapsack isn't actually polynomial.

DFS takes in $n + m$ "objects" as input. If we say that each object takes a fixed number of bits (e.g., each vertex takes 1 bit to encode and each edge takes 3 bits), then it makes sense to me that the algorithm is indeed polynomial in the input. But is there any reason that we need a fixed number of bits for each object? Might there exist a more powerful encoding of the input that takes $\log (m+n)$ bits, suddenly making the algorithm exponential?

One thought I had was just that there is an assumption that any practical encoding in the real world is going to require a fixed number of bits for every extra "object" given as input, whether the objects be vertices, letters in a string, etc.; thus it is most useful to think about runtimes this way. But I want to make sure since I think this is fundamental to my understanding. Thanks in advance!

There are $2^{n^2}$ labelled directed graphs on $n$ vertices.  Therefore, any such graph requires at least $n^2$ bits to represent it.  So, there is no hope for an encoding scheme that always uses at most $O(\log n)$ bits and can encode all graphs.

If you want to focus on labelled directed graphs with $n$ vertices and $m$ edges, there are ${n^2 \choose m}$ of them, which for $m \ll n^2$ is approximately $(e n^2/m)^m / \sqrt{2\pi m}$, and thus you'll need at least $m \lg (n^2/m) + O(m)$ bits to represent all of them.  Notice that this is $\Omega(m)$, so there is no hope for an encoding scheme that uses only $O(\log m)$ bits (or $O(\log(m+n))$ bits) and can represent all such graphs.

Of course, you can consider encodings that are logarithmically short, but they can only express a tiny fraction of all possible graphs.  Yes, if you wanted to represent the input in that way and solve a reachability problem on such a graph, then ordinary DFS would take time exponential in the size of the input.

Related: You might be interested in succinct data structures.


How can I compute the time complexity of this image processing algorithm? Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing.

I simplified the algorithm ... so that we focus only on the problematic part.

Algorithm

You have an image/matrix of $N =n \times m$ size and a block of size $b \times b$ (block is just a window or rectangle that will slid through the picture of pixels or the matrix of intensities).

The algorithm goes through most pixels in the image (as center of the block, so it may step over the end of the line or the beginning) by a step of size $s$. The step is inferior to the size of the block $s<b$, so there is some overlapping (because some pixels are being considered in multiple blocks), and then it performs some operations with a complexity relative to the size $b$ equals $O(b^2)$.

Concretely, the algorithm starts in line $1$, and process blocks starting at $1, s+1, 2s+1, ... $ columns, then it goes to the $s+1$ line and do the same as on line $1$, then to $2s+1$ line and so on. Every iteration, the algorithm computes some operations related to the size of the block (which can be $3 \times3$ or $5 \times 5$, ... and $s$ is $1/8$ the $b$ for instance).

Any help, or reference related to this topic is a welcome.

We need to estimate how many times block operation is performed.

First lets answer in how many rows we will start block processing - easy to see that each $S$ row are taken into account, so answer to this sub-question is $O(N/S)$. If we suppose that $N$ - number fo rows and $M$ number of columns.
Then we need answer to question - how many times we will run block processing for each row, due to we perform processing of blocks that starts only in each $S$ columns - answer for this sub-question will be $O(M/S)$.

Now we have that block processing will be performe $O(N*M/S^2)$ times for whole input. And result time-complexity for whole algorithm will be $O(N*M*B^2/S^2)$.