texts: If A is mapping reducible to B and A is recognizable, then is B recognizable too?

texts:
I learned the proof for the theorem:
If A $\leq_m$ B and B is recognizable, then A is recognizable
and was provided with the theorem:
If A $\leq_m$ B and A is unrecognizable, then B is unrecognizable

So does this work both ways? i.e. does this also hold?

If A $\leq_m$ B and A is recognizable, then B is recognizable
If A $\leq_m$ B and B is unrecognizable, then A is unrecognizable


texts: Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1

texts:
So if $k = 3$ and $n = 2$ and we select the element $a_1[3]$ of the first array then we have to select $a_2[1]$ from the second array. If we select the element $a_1[2]$ then also $a_2[2]$ must be selected etc.

I can think of a DP algorithm to solve that which takes $O(nk)$ time (I don't think that I need to describe it, it's fairly easy to think). But I don't know if binary search can be used to find the answer more efficiently.

This may sound like a weird problem but it's part of a DP algorithm I'm trying to figure out and so the complexity will be multiplied with $kn$ so it would be great if I found a solution with $O(k)$ complexity.


texts: How to choose the maximum number of nodes (with constraints) from a graph

texts:
Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$.

A positive integer $x$ is given and you want to choose at most $x$ nodes so that

There is a path connecting all the nodes you choose that doesn't visit any node you haven't chosen.  A path can backtrack. This is to say the set of vertices you choose induces a connected subgraph in $G$.
Each node you choose has weight at least as great as all nodes you haven't chosen.

The goal is to maximize the number of nodes you choose.

Is there  a fast algorithm for this problem?


texts: Converting if-then-else condition to integer linear programming with equality constraints

texts:
I have an if-then-else condition with three binary variables $A$, $B$ and $C$:

if A = 1
       then B = 1
else
       B = C

How do I express this as an integer linear program with equality constraints?


texts:
Does there exist an equivalent arithmetic circuit for each computable function?

I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe the statement to be false.

What has made me curious is that I've read some theorems stating that a protocol (cryptograhy protocol theory) can compute any computable function, but then requires that the function should be specified as an arithmetic circuit.


texts:
i was wondering:

is this language in class P?

$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$

explanation: a word $<A,B>$ belongs to the language if A and B are descriptions of finite deterministic automatas that the languages they identify are not foreign to each other

so in order to be in class P, the given language needs to be "solved" by a deterministic turing machine in polynomial time.

i tried to research this language but did not came with anything and i am not sure how to build simple algorithm(turing machine) that runs on both and verifies that there is at least common element and then maybe prove in induction for the rest. but that seems not very efficient.

i know that if $L(A)=L(B)$ then i can just build a turing machine that goes over the DFA. and if one is contained in the other, so i do a union of that DFAS and then i can build a turing machine that goes over both, but i am sure i am missing a lot of things and this is not a formal proof.

would really appreciate your help with this


texts: Length of shortest codeword in Huffman encoding

texts:
Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1?

I thought of 2 cases where this might be true, but they're not exactly proofs -

Case 1: There is only one character which occurs more than 1/3rd of the time. In this case, a good huffman encoding scheme will ensure that this character corresponds to a single-character encoding, because there are no competing characters. Even though there may be characters that occur with high probability (but still less than 0.33), they must have length greater than 1 to ensure the prefix-free nature of the encoding.

Case 2: There are multiple characters that occur more than 33% of the time. We can also make the stronger assertion that in this case, there can only be at most 2 such characters. This can be further subdivided into cases where 1) there are a total of 2 characters in the encoding scheme, and 2) where there are more than 2 characters in the scheme. In case 1), both the characters can correspond to a single-character encoding scheme (0 and 1 for each respectively). In case 2), at most 1 of the 2 largely prevalent/frequent characters must have an encoding of length of 1  (since we're considering a good huffman encoding scheme) while the other n-1 characters have a length of at least 2.

I'm afraid that this is not the right approach. Could someone please help me out?


texts: Can I simplify log(n+1) before showing that it is in O(log n)?

texts:
Had a question about the following:

$$\log (n+1) \in O(\log n)$$

Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?


texts: simple uniform hashing: unclear definition of probability

texts:
I am trying to understand the assumption of Simple Uniform Hashing (SUHA) as e.g., in CLRS textbook; or other courses about hashing.

The usual description given to SUHA is (cf. CLRS):

  "we shall assume that any given element [i.e., key] is equally likely to hash into
  any of the m slots, independently of where any other element has
  hashed to. We call this the assumption of simple uniform hashing."

However this is quite informal, and thus I don't fully understand it.
My understanding is that the assumption supposedly means that

$ Pr[h(k)=\ell]=1/m\,$, for any given key $k$ and slot in the table $\ell=0,\ldots,m-1$, where $m$ is the number of slots in the table.
But since given a key $k$ the deterministic hash function $h$ is fixed on $k$, there is no probability distribution here!

Perhaps it is meant here that $k$ is a random variable distributed uniformly over all keys?

  Question: what is the distribution the probability $ Pr[h(k)=\ell]=1/m\,$ is defined over in SUHA?

EDIT:

My understanding is the SUHA is an (idealized) assumption that formally means that the probability $Pr[h(k)]$ is the probability of the event of inserting a key to the table nevertheless the time of insertion (it might be the first key I insert or the last one).

In other words, the sample space of probability $\Omega$ is

$\Omega:=($the set of all [ordered] sequences of insertions to the hash table$)$.

The probability event $h(k)=\ell$ is thus the set of all [ordered] sequences of insertions to the hash table in which the $n+1$th insertion hashes to $\ell$, where $n+1$ is the ``current'' insertion that I'm analyzing and where $n$ is the current number of keys in my hash table.

In SUHA we shall also assume that $h(k)=\ell$ for every $n$ (the current position of insertion in the sequence); namely, we assume that the event $h(k)=\ell$ is completely independent of the sequence.

  To sum up the answer: the probability $Pr[h(k)=\ell]$ is taken over
  all possible ordered sequences of insertions to the hash table.


texts: In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a $T$ exists. Then, we consider a case where we restrict $i$ to $M$ itself, and then derive a contradiction by using an instance of a diagonal argument. I am interested how would the proof go if we are given a promise that $i \not = M$? What about promise $i \not = M^\prime$, where $M^\prime$ is functionally equivalent to $M$?


texts: How to decompose a unit cube into tetrahedra?

texts:
I was presented with the problem of breaking the unit cube $[0,1] \times [0,1] \times [0,1] $ into tetrahedron shapes.  The first two pieces are easy, but it's not so easy to visualize after that.  I found:

$\{ (0,0,0), (1,0,0), (0,1,0), (0,0,1) \}$
$\{  (1,1,1), (1,1,0), (1,0,1), (0,1,1) \}$

What remains is a triangular prism.  Then maybe I think it readily splits into 2 or 3 pieces.  In any case, they are difficult to draw and keep track of all the data.

Also I think I could have started differently with this other tetrahedron:

$\{ (0,0,0), (1,1,0), (0,1,1), (1,0,1) \}$

There should be lots of solutions, but I neither have the date to store into a computer nor do I have picture of even a single one.


texts: Circle Intersection with Sweep Line Algorithm

texts:
Unfortunately I am still not so strong in understanding Sweep Line Algorithm. All papers and textbooks on the topic are already read, however understanding is still far away. Just in order to make it clearer I try to solve as many exercises as I can. But, really interesting and important tasks are still a challenge for me.

The following exercise I found in lecture notes of Line Segment Intersection by omnipotent Jeff Erickson.

  Exercise 2. Describe and analyze a sweepline algorithm to determine, given $n$ circles in the plane, whether any two intersect, in $O(n \log n)$ time. Each circle is speciﬁed by its center and its radius, so the input consists of three arrays $X[1.. n], Y [1.. n]$, and $R[1.. n]$. Be careful to correctly implement the low-level primitives.

Let's try to make a complex thing easier. What do we know about intersection of circles? What analogue can be found with intersection of lines. Two lines might intersect if they adjacent, which property two circle should have in order to intersect? Let $d$ be the distance between the center of the circles, $r_{0}$ and $r_{1}$ centers of the circles. Consider few cases:

Case 1: If $d > r_{0} + r_{1}$ then there are no solutions, the circles are separate.
Case 2: If $d < |r_{0} - r_{1}|$ then there are no solutions because one circle is contained within the other.
Case 3: If $d = 0$ and $r_{0} = r_{1}$ then the circles are coincident and there are an infinite number of solutions.

So, it looks like conditions of intersection are ready, of course it may be wrong conditions. Please correct if it's so.

Algorithm. Now we need to find something in common between two intersecting circles. With analogue to line intersection, we need to have insert condition and delete condition to event queue. Let's say event point are x coordinate of the first and the last points which vertical sweep line touches. On the first point we insert circle to status
 and check for intersection (3 cases for checking are mentioned above) with nearest circles, on the last point we delete circle from status.

It looks like is enough for sweep line algorithm. If there is something wrong, or may be there is something what should be done different, feel free to share your thoughts with us.

Addendum:

I insert a circle when vertical sweep line touches the circle for the first time, and remove a circle from the status when sweep line touches it for the last time. The check for intersection should be done for the nearest previous circle. If we added a circle to status and there was already  another circle which we added before and it was still there, therefore the pervious circle was not "closed", so there might be an intersection.


texts:
In Haskell, the Monads type class has the bind operator, which is represented by the symbol >>=

The type of such operator is:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

Why does the function need to be (a -> m b)? Why functions the preserve che inner data type (a -> m a) are not allowed?

Has this choice been made for some convenience in the language design, or does it have some other reason?


texts:
So the question is

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to the right.

This is a common interview question on software engineering interviews, it is easily solved by implementing a dynamic programming table in order to discern what path is the least costly.
I am now wondering, is there an easy way to solve an alternative problem? Which would be to find the exact sum of a path in an mxn grid.
For instance the input would be a 3x3 matrix and the target sum would be lets say 4. What type of technique should be used in order to find a path that equals exactly 4 to the bottom right corner from the top left corner.


texts: A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular

texts:
For a given language $L$ and $w \in X^{\ast}$ denote by $w^{-1} L := \{ u \in X^{\ast} : wu \in L \}$ the (left) quotients of $L$. The left quotients are closely related to the minimal automaton of $L$ in case $L$ is regular, i.e. in that case $(X, Q, \delta, q_0, F)$
with $Q := \{ w^{-1} L : w \in X^{\ast} \}$, $\delta(w^{-1}L, x) := x^{-1}(w^{-1}L)$,$F := \{ w^{-1}L \in Q : \varepsilon \in w^{-1}L \}$ is isomorphic to the minimal complete automaton accepting $L$.

I am interested in the minimal automaton of a given quotient $w^{-1}L$ in case $L$ is regular, is there a way to construct it? Also as the quotients and the states in a minimal automaton correspond to each other, I am somehow interested in the set $\{ u^{-1}(w^{-1}L) : u \in X^{\ast} \}$ for  given quotient $w^{-1}L$.

Note also that the quotients are closely connected to the Nerode (right) congruence, i.e. $u \sim_L v \Leftrightarrow \forall x \in X^{\ast} : ux \in L \leftrightarrow vx \in L \Leftrightarrow u^{-1}L = v^{-1}L$, giving a bijection between them; and also yielding that the minimal automaton of $L$ is an accepting automaton for the nerode classes.


texts: Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number sufficiently close to $M$?


texts: Can a graph have a cycle containing all nodes but not Hamiltonian?

texts: Is it possible for a graph to have a cycle that goes through all the nodes, but it does not have a Hamiltonian cycle (i.e. the cycle goes through some nodes more than once)? If yes, can anyone prove it? If not, can anyone give a counterexample?


texts:
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?

I am really stuck and I tend to believe it's true, but I don't know how to prove it.

Any help would be appreciated!


texts: Does a new stack get created for each async callback internally?

texts:
I am thinking about JavaScript here, or any language that supports async IO or that sort of thing (coroutines? though don't have much experience with those).
I have looked at some of the resources below in trying to figure out how the stack works when you have async, but I don't understand it yet and don't quite follow some of the inner details of the posts.
Basically, when you have something like this, what happens?
setTimeout(() => {
  process() // takes a few milliseconds let's say
  setTimeout(() => process2(), 2)
  setTimeout(() => process3(), 1)
}, 2)
setTimeout(() => process4(), 2)

Does a new stack get created for each callback? You could have an example using async / await and Promises too, I think it would work the same.
By that I mean, not just a stack frame but a completely new stack? When the async callback comes back, a new stack is created. When that stack hits a new async function it just moves past it to the next function like normal. But wait, it has to keep track of the parent scope, so when the first function is "done" executing its synchronous stuff, its stack stays open in some ways because the callback needs access to its scope. How much of the stack remains? Then the callback executes, maybe calling another few nested async callbacks. Etc.
So what happens to the stack(s) exactly?

Is there more than one stack getting created? If so, when and where?
If so, how do the stacks get cleaned up generally speaking?

In my head there is some sort of tree structure being created asynchronously, but (a) I don't know if that's true, and (b) if it was true, I don't know what it would look like exactly or how it would function.
Resources:

https://stackoverflow.com/questions/56241258/working-of-call-stack-when-async-await-is-used
Is a stack structure used for async processes?
https://lewissbaker.github.io/2017/09/25/coroutine-theory
https://stackoverflow.com/questions/23406584/how-is-asynchronous-callback-implemented
https://stackoverflow.com/questions/42287737/how-do-yield-and-await-implement-flow-of-control-in-net/42291461#42291461
https://docs.microsoft.com/en-us/archive/msdn-magazine/2013/february/async-programming-async-causality-chain-tracking
https://en.wikipedia.org/wiki/Parent_pointer_tree
https://en.wikipedia.org/wiki/Coroutine
https://www.mikemarcin.com/post/coroutine_a_million_stacks/
https://gcc.gnu.org/wiki/SplitStacks
https://agis.io/post/contiguous-stacks-golang
https://without.boats/blog/futures-and-segmented-stacks/

Since coroutines can be suspended without destroying the activation frame, we can no longer guarantee that activation frame lifetimes will be strictly nested. This means that activation frames cannot in general be allocated using a stack data-structure and so may need to be stored on the heap instead.


texts: Does proving a problem is in P typically mean it will eventually be practically solvable?

texts:
I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P and NP.

First he says:

  $P$ roughly corresponds to the class of problems that are realistically
  solvable on a computer.

He then continues a little further down the page:

  Of course, a running time of $n^{100}$ is unlikely to be of any practical use. Nevertheless, calling polynomial time the threshold of practical solvability has proven to be useful. Once a polynomial time algorithm has been found for a problem that formerly appeared to require exponential time, some key insight into it has been gained and further reductions in its complexity usually follow, often to the point of actual practical utility.

So my question is the following: What are examples of problems that were proven to be in P but were intractable, but after some theoretical advances became tractable?

I'm also welcome to hearing about problems that were proven to be in P whose runtime was significantly advanced by some algorithmic improvements but perhaps was not advanced enough to be tractable.


texts:
What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network?

As I recall your basic neural network is a 3 layers kinda thing,
and I have had Deep Belief Systems described as being neural networks stacked on top of each other.

I've not til recently heard of a Deep Learning Systems, but i strongly suspect it is a synonym for Deep Belief System. Can anyone confirm this?


texts: Chomsky normal form and regular languages

texts:
I'd love your help with the following question:

  Let $G$ be context free grammar in the Chomksy normal form with $k$
  variables.

  Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ?

What is it about the amount of variables and the Chomsky normal form that is supposed to help me solve this question? I tried to look it up on the web, but besides information about the special form itself, I didn't find an answer to my question.

The answer for the question is that $B$ might be regular.


texts: Need help with a very specific Greedy Algorithm. Are there fast solutions?

texts:
i need help for a specific problem i have at work.
You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000:
Row 1 might look like: [1,288,399,784,456,994].
Row 2 might look like: [4,784,123,8]
For each each element in each row, we take the mod 8, and obtain a distribution. In this case, it would be [3,1,1,0,0,0,0,1] , where each element represents the sum of that the values with that mod index. (3 elements had %8 = 0)
Row 2's distribution would look like [2,0,0,1,1,0,0,0]
We define the max of this list to be the 'size' of the row. In this case, the max size would be 3. The overall goal is to sum up the lengths of each row and achieve a minimum total size.
One Caveat is that we are able to swap any two numbers. In the original example, we can swap 288, 784, or 456 with some other index, lets say 581 with 784. Now, our distribution would look like [2,1,1,0,0,1,0,1], and we've successfully reduced the size of this row. However, any other row containing 581 or 784 must also be swapped, so we might have introduced a greater size to other rows.
For example, row 2 now looks like [4,581,123,8] after the swap. Now row 2's distrbution looks like: [1,0,0,1,1,1,0,0]. In this case, we might have decreased the size of row 2 as well! However, you can imagine that this might have just as well also increased the size of many other rows, so the overall size would increase.
I'm trying to figure out if there is a fast/greedy way to figure out what the optimal swaps are to minimize the sum of all the sizes. I'm lacking context on if there are any algorithms i should look at that solve this kind of problem. Please let me know if the clarification is necessary.


texts:
Is the halting problem decidable for TMs that do not write to the tape?
Once a read only tape TM repeats a configuration, it will loop forever. Therefore, all we have to do to decide the above is construct a different TM(with read and write tape) that’s takes the read only TM as input and checks for a repeat configuration, if one is found, accept, otherwise reject.
Is this correct?


texts: Is there a meta text processing concept in CS?

texts:
I understand that text processing could be done in various ways on top of operating systems:

Shell utilities for processing a file (and/or a file name): tr, sed, awk, perl, mv and others
text editors for processing a file (and/or or a file name): nano, Vim, Emacs and others; whether CLUI/TUI/GUI and whether for "plain" or "rich" text
Possible shell builtins: such as compgen to to generate auto-completion matches for specified commands and possibly others

I further understand that generally all of these programs can be empowered by what I can name "meta text processing" implementations such as regex and serialization (for example; JSON key-value pairs).

Is there a meta text processing concept in CS (and what might be a practical example besides regex and serialization)?

I am hoping to find theory regarding text processing, or computer data processing. I don't expect an answer such as "you could use YAML instead JSON".


texts: How to proof that this ratio isn't the finite transformation?

texts:
How to check if the ratio is given: $a^{m}b^{n}a^n \rightarrow a^{m}b^{n}a^{m}$ by finite transformations?
I tried using the pumping lemma for finite transducers, but that didn't get me anywhere. Which way should I think?


texts: Should we eliminate left recursion before using NPDA to simulate CFG?

texts:
I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser".
It says:

If a language is context free, then some pushdown automaton recognizes it.
Let A be a CFL. From the definition we know that A has a CFG,
G, generating it. We show how to convert G into an equivalent PDA, which we
call P.

But what if G has left recursion?
Does the NPDA construction in this book can halt when it simulate a CFG which has left recursion?
What's the different between NPDA and Recursive-Descent Parsing (full backtracking) in Compilers Principles, Techniques, & Tools ?
Thanks.


texts:
I am curious as to what the maximum data transmission rates are to a given frequency.

Say you have a com channel with a frequency of 10 khz. How many bits/s would you be able to send?

Thanks!


texts: circle packing algorithm used by Percolator

texts:
I was admiring this rendition of the Mona Lisa from quasimondo's Flickr account.  He says:

  Combining circle packing with data visualization. The pie charts show
  the distribution of the dominant colors under the circle area.

  The circle packing technique used here is a combination of an image
  segmentation with a distance transform and the first one who came up
  with it is John Balestrieri: www.flickr.com/photos/tinrocket/

I have traced it to an app called Percolator

How are such circle packings calculated? How are the pie charts calculated from the image?


texts: Recursive set - How to show a language is undecidable

texts:
I am currently working on the following task:

A language L = {< M> | M(x) = x^2} is given. Now I need to show, that this language is not decidable.
 By the way, < M> is the Gödel number

But right now, I don't know how to deal with that task. Honestly, this is the first time that I am working with this kind of task.

I would appreciate if you could give me some hints, because I don't know how to proceed with the task.


texts:
Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$?

I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of having two "gadgets": the 2-node variable gadgets and 3-node clause gadgets.

I also understand the formula $k = variables + 2\:clauses$ as the minimum number of nodes required to cover all the edges. What I don't understand is how this setup proves that if there exists a $k\text-covering$, then the boolean expression in CNF is satisfiable.

Examples with expressions that are satisfiable and not satisfiable would be helpful. Also, once the $3SAT$ problem is converted to a $k\text-covering$, does it provide a means to identify which value (true or false) should be assigned to each variable so as to satisfy the boolean expression?


texts:
Are there program systems that can discover the need of routines - and then design them, code them and use them as parts of the system?

Any group of humans trying to pursue an activity has to develop in a developed system, to solve their problems by formulating the issues, search for knowledge and methods, to be tested and evaluated - and to be incorporated into the common experience for the activity to be pursued. Are there some software that could be compared with a human process like that?


texts: Compression functions are only practical because "The bit strings which occur in practice are far from random"?

texts:
I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question.

Andrej explains that given the set of all bit strings of length 3 or less, a lossless compression function can only "compress" some of them. The others, for instance "01" would have to actually be compressed to a string such as "0001", with length 4. The compression ratio is simply the average compression across the input set.

This makes lossless compression seem impractical, but the important quote is this:

  The bit strings which occur in practice are far from random and exhibit a lot of regularity.

I have a hard time believing that, for instance, multimedia files are represented by anything other than random bit strings. Is there truly a pattern that compression functions leverage to make the algorithm useful in reality?


texts:
In "Call-by-push-value: A subsuming paradigm." (Levy, Paul Blain. Springer, Dordrecht, 2003. 27-47) terms of the lambda calculus get split in to values and computations, with the slogan "A value is, a computation does".

What I don't understand is: why are abstractions computations and not values? Intuitively a function does not do anything and can be used as data. It will only do something when applied to something.


texts: Is there a general algorithm to fill holes in terms of the Calculus of Constructions?

texts:
Suppose that you extend the Calculus of Constructions with "holes" - i.e., incomplete pieces of code that you didn't fill yet. I wonder if there is an algorithm to fill those roles automatically. For example (using Morte's syntax):

Case A:

λ (pred : ?)
-> λ (Nat : *)
-> λ (Succ : Nat -> Nat)
-> λ (Zero : Nat)
-> (Succ (pred Nat Succ Zero))

On this situation, a type inference algorithm can identify that ? can obviously only be ∀ (Nat : *) -> (Nat -> Nat) -> Nat -> Nat, because pred receives Nat : *, Succ : Nat -> Nat, Zero : Nat, and must return Nat, because it is the first argument of Succ.

Case B:

(Id ? 4)

Where 4 is λ-encoded and Id is the identity function (i.e., ∀ (t:*) -> λ (x:t) -> x). On that situation, ´?´ is again clearly ∀ (N:*) -> (N -> N) -> N -> N, because that is the type of 4.

Case C:

(Id (Equals Nat 7 (add 3 ?)) (Refl 7))

Here,Equals and Refl are defined in a similar fashion to Idris. ? can obviously only be 4, but how do you figure that out? One way would be using the fact that ? : Nat, and Nat is a type which we know how to enumerate, so we can just try all Nats til it typechecks. That can be done for any enumerable type.

Case D:

(Id (Equal Nat 10 (MulPair ?)) 10)

Here, ? can only be of type Pair Nat; it has only more than one valid answer, though: it can be (Pair 10 1), (Pair 2 5), (Pair 5 2) and (Pair 1 10).

Case E:

(Id (Equal Nat 7 (Mul 2 ?)) 7)

Here, there is no valid answer, since 7 isn't a multiple of 2.

All those examples made me notice that we can make a general algorithm that identifies some known patterns and gives an answer by handpicking a specific algorithm (type inference, brute-force, and so on), kinda like Wolfram Alpha figures out the right strategy to solve an Integral. But that sounds like an engineering/hardcoded approach. Is there a principled way to solve this problem? Is there any research study/area on it?


texts: Amortised analysis of binary heap insert and delete-min

texts:
I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function.

We can assume, that insert is O(logn) and delete-min is O(logn) too.

The goal is to prove, that amortised price of insert is O(logn) and amortised price of delete-min is O(1).

Can't figure out how to create a potential function.

POT.F = ?
INSERT c = logn + (something from 0 to xlogn)
DELETE-MIN c = logn + (something like -logn)

Could you guys help me? I've figure out so far that difference between potentials should be from 0 to xlogn so INSERT price would be logn and for DELETE-MIN, difference should be somewhere abour -logn to get constant price.


texts: Space usage of recursive functions with no return

texts:
Consider an algorithm for reversing a sequence given below:
def reverse(S, start, stop):
    if start < stop − 1:
       S[start], S[stop−1] = S[stop−1], S[start]
       reverse(S, start+1, stop−1)

The time complexity of this algorithm is $O(n)$ because we make $n$ recursive calls each taking at most $O(1)$ time.
But what about the space complexity, It seems that the space complexity of a recursive function is equal to the number of recursive calls. I see that we make $n$ recursive calls but can the space complexity be $O(n)$ when we are not returning to the calling function (no return)? In other words, why not just delete the activation frame when we jump to the next one since we do not need it anymore because we have no more work to do there.


texts: A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard?

texts:
The multiple choice knapsack problem (MCKP) can be defined as follows:

MCKP is known to be NP-hard in general. I have a special case of MCKP for which

$N_i=\{1,2,\cdots,|N_i|\}$, for all $1\leqslant i\leqslant k$ ;
$p_{ij}=j$, for all $1\leqslant i\leqslant k$ and for all $1\leqslant j\leqslant|N_i|$; and
$w_{i1}<w_{i2}<\cdots<w_{i|N_i|}$, for all $1\leqslant i\leqslant k$.

My question is: Can we solve this special case of MCKP in polytime? (Or, is this special case of MCKP NP-hard?)


texts: NP-Completeness of a Graph Coloring Problem

texts:
Alternative Formulation

I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to describe the problem. However, I believe that the alternative formulation is still NP-hard. The alternative formulation uses a disjoint set of incoming and outgoing nodes that simplifies the problem definition.

Given $n$ outgoing and $n$ incoming nodes (the red and blue nodes in the figure respectively), and a set $w_{ij}$'s of size $n \times n$ of edge weights between the outgoing and incoming vertices. The goal of the problem is to color the thick edges in the figure so that for every incoming node, a condition holds.

  Given a set $\{ O_i \; | \; i=1 \dots n \}$ of output vertices, a set $\{ I_i\; | \; i=1 \dots n \}$ of input vertices, $n \times n$ weights
  $w_{ij} \ge 0$ between $O_i$'s and $I_j$'s for $i,j=1 \dots n$, and a positive
  constant $\beta$, find the minimum number of colors for the edges
  $e_{ii}$ (thick edges in the above figure) such that for all $j=1 \dots n$,

  $$ \frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta $$

  where $c(i)$ shows the color of the edge $e_{ii}$.

Old Formulation

The following problem looks NP-hard to me, but I couldn't show it. Any proof/comment to show the hardness or easiness of it is appreciated.

  Assume $K_n=\langle V,E \rangle$ is a complete weighted directed graph
  with $n$ nodes and $n(n-1)$ edges. Let $w_{ij} \ge 0$ show the weight
  of the edge $ij$ and $c(ij)$ shows the color of edge $ij$. Given a subset
  of the edges $T \subseteq E$ and a positive constant $\beta$ the goal is:
  find the minimum number of colors such that for each $e_{ij} \in T$:

  $$ \frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta. $$
  and
  $$ c(ij) \neq c(ik) \quad for \quad j \neq k $$

Please note that in the above problem, only the edges in $T$ needs to be colored. That is the problem can be solved in $\mathcal{O}(|T|!)$.

Update:

After Tsuyoshi Ito's comment I updated the problem. The denominator is changed from $1+\sum_{c(kj)=c(ij),k \neq i,e_{kj} \in T} w_{kj}$ to $1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}$. Therefore, the denominator contains the weights outside $T$ as well. That's actually why I mentioned the complete graph in the definition.

I also added an additional constraint $c(ij) \neq c(ik) \quad for \quad j \neq k$. That means, the outgoing edges from a node must be of different colors (but the incoming colors can be the same as long as the inequality holds). This puts an intuitive lower bound on the number of colors, which is the maximum out-degree of the nodes in $T$.

As Tsuyoshi mentioned, $w_{ij}$'s, $T$, and $\beta$ are inputs to the problem and the edge colors are the output.

Update 2:

Problem does not enforce the edges $e_{ij}$ and $e_{ji}$ be of a same color.


texts: How can an 8-bit computer have a 20-bit address bus?

texts:
I'm in the middle of building a homemade processor from logic chips, and I've been trying to figure out how I can have RAM (for main memory) and ROM (for small booting stuff) on the bus at the same time. I came up with memory mapped I/O, but how do i make my 8-bit processor have a 20-bit address bus? (enough lines for 64 kiB of memory and 4 extra for decoding)

Or should i maybe have dedicated enable lines for RAM and ROM coming out of my instruction decoder?

Thanks.


texts: Context switching in M:N threading models?

texts: I wanted to know how M:N kernel user thread model handles context switching, between multiple khread and pthread. How does the PCB/TCB for process and threads look like, how is state of registers stored while switching between kernel mode and user mode or vise versa, or between kernel threads or between user threads.Any help or reading directions would be helpful. Thanks.


texts: How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?

texts:
How to treat $\epsilon$ and '\$' in top-down parser using predict table?

The construction of the predict table

  Given a product $X \rightarrow w$, row $X$ and column $t$
  -Mark $X \rightarrow w$ for each $t \in FIRST(w)$
  -If $NULLABLE(w)$, then mark $X \rightarrow w$ for each $t \in FOLLOW(w)$ as well

says to create columns for all terminal symbols. $\epsilon$ is a terminal symbol so it's naturally added as a column.

However, I've somehow interpreted that I could/should add '\$' as a terminal symbol as well. Basically because '\$' is used in the FOLLOW sets (and the FOLLOW sets don't contain $\epsilon$).

But does this create redundancy since then the table would hold basically the same predict rules for '\$' and $\epsilon$ (at least in the implementation I have here)?

The rules given here also treat '\$' and $\epsilon$ as if they were separate:
http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

The FOLLOW sets basically use '\$' in place of $\epsilon$, but the predict table uses $\epsilon$, because it's a terminal symbol.


texts: King of the North: Placing bannermen surrounding castle

texts:
I was trying to solve the King of the North problem in Kattis. Basically, the problem is, the king has a castle to protect. To do this, he wants to place bannermen across the open areas surrounding the castle (some parts are closed thanks to natural barriers).

A more detailed description of the problem:
Given a grid of $R$ rows and $C$ columns, where one square contains our castle and some contain walls. We can place bannermen, who can blockade a square. Each open square has a different amount of bannermen required to form a blockade, which is given. Our task is to determine the minimum amount of bannermen that have to be fielded such that the castle is unreachable from the edge of the grid. (walls and blockaded squares are impassable)

Please go through the attached link for an even more detailed (and colourful) description of the problem.

My idea to solve this:

  Go to each outermost corner of the map. From each of these points, do a A* search. This will give the shortest path from the point to the
  castle.
  For each such point on the shortest path, try to see which ones are 'critical' - meaning placing bannermen on those points will force the
  enemy to take a longer path.
  Among all such critical points, see which ones need lesser bannermen.

Anyone has a better idea?

I do not like my approach, particularly because it involves heuristics, and I am not sure whether it is correct.


texts: Determining if an undirected connected graph is minimally connected

texts:
I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused.  The question is to determine if an undirected connected graph is minimally connected.

The authors define minimally connected as "it is connected and there is no edge that can be removed while still leaving the graph connected."

This question is equivalent to asking if there are any cycles in the graph.

They authors' solution runs the white-gray-black variant of recursive DFS, and return false if a grey node is visited twice.

It seems to me though, that since you know the graph is connected you can just count the number of edges.  Any minimally connected graph, like a binary tree, will have (V - 1) edges.

return num_edges/2 == num_vertices - 1;

So, long story short, is this solution correct for the case of an undirected, connected graph?  I checked the books errata and it doesn't mention it.


texts: Universal hash function for strings of unbounded length

texts:
Is there a (weakly) universal hash function for strings without any assumption of the string length?
I did not find one on Google / Wikipedia.


texts: Constraint propagation using Projection rule

texts:
I've found this example of constraint propagation using projection rule

We have

C = { x1 ≠ x2, x1 ≥ x2 }

< C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} >

They say that applying propagation rule, does not give any simplification.

I'm not sure why this is the case. Shouldn't we get?

< C; x1 ∈ {2,3}, x2 ∈ {1,2} >

Other steps in the example, make sense that to me, e.g.

< C; x1 ∈ {2}, x2 ∈ {1,2,3} >

produces

< C; x1 ∈ {2}, x2 ∈ {1} >


texts:
Given the following page table with a 24 Bit virtual address and 4KB page size and 4 byte long entries (%X means hexadecimal values):

I don't understand how to translate e.g. address %X00ABBA here. I really tried but I don't understand. I know I have 12 bits for the VPN, so I take 00A and look it up in the page table. But how do I look it up here? V = Valid Bit, M = Modify Bit, COW = Copy-on-Write Bit, PFN = Page Frame Number

Can you help me, please?


texts:
I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each having a weight and volume capacity, where these items need to go inside. A feature that I am looking for is that the value property of each item which depends on which knapsack it goes into. For instance, item 1 has value of v1 if goes into knapsack 1, and v2 if it goes to knapsack 2.

How can I model the problem as a knapsack and an optimization problem so to maximize the overall value? So far I came into a multiple knapsack problem, 2 dimensional. For for the value, I don't have any clue.


texts: Time/Space Optimal k-Subset Operator Application - Is this a named problem?

texts:
I have searched extensively and unsuccessfully for references to a
combinatorial problem that arises in my work. I am hoping someone
can tell me if this type of problem has a "name" and provably optimal solutions.

The problem: Given a set of objects denoted by $X_1,\ldots,X_N$, a commutative
and associative operator $\oplus$, and $K \leq N$, generate all $N \choose K$
subset-applications of the operator in a way that first minimizes the number of
operator applications, and then minimizes the number of partial results that
must be stored, assuming that once a complete combination is generated its
storage can be recovered. For example, for $5 \choose 4$ we need to generate the five
new objects
$$
X_1 \oplus X_2 \oplus X_3 \oplus X_4, \\
X_1 \oplus X_2 \oplus X_3 \oplus X_5, \\
X_1 \oplus X_2 \oplus X_4 \oplus X_5, \\
X_1 \oplus X_3 \oplus X_4 \oplus X_5, \\
X_2 \oplus X_3 \oplus X_4 \oplus X_5 \\
$$
which naively requires 15 operator applications and a single
accumulator. However a better solution
requires only 11 operator applications if storage is allocated for 3 partial
results.

Note that no negation or inverse of the operator $\oplus$ is assumed.  This rules
out using most popular combination-generation schemes such as Gray codes. In
the motivating application the operator is also idempotent ($X \oplus X = X$)
but I don't think this fact is helpful to a solution.

I have developed a good algorithm to solve the problem
using at most $N$ accumulators.  However it strikes me that others have
probably analyzed this type of problem and I simply don't know the correct
terminology to guide my search.


texts: Whats the difference between an oracle and a decider in Computational Theory?

texts:
I'm learning about Turing reductions at the moment and I'm just wondering is there any difference between an oracle and a decider, As they seemingly do the exact same thing. I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

  An oracle for a language B is an external device that is capable of reporting whether any string w is a member of B

which is the exact same thing as what a decider does. Is there any sort of difference between the two?


texts: Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy

texts:
I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise to the reader. Even Stockmeyer's original paper on the hierarchy (this one, right?) proves the result in a "Remark." section, so it's not exactly the most detailed proof.

Just so we're clear, i did write my own version of the proof; it's exactly because of all the work i had to do in order to prove said result, contrasted with the one-paragraph proofs commonly found in the literature, that makes me curious about what kind of insight i might be missing.

As for how my proof proceeds, i can give an high-level overview of the harder direction. Using the certificate version of the hierarchy, and second-order logic with alternating quantifier blocks, the proof goes by induction. Base case is Fagin's Theorem. For the inductive step, you have a second-order formula deciding the input+certificate relation, so all you need to do is to introduce some existential quantifiers over the given formula quantifying all of its relational symbols, plus a formula that states that the interpretation given by the quantifiers does contain the input.

Of course, like any high-level overview, this is easier said than done. At least in my proof, there's a fair amount of translating in order to make things work. Plus there's the fact that the usual certificate definition is over languages, and we're dealing with arbitrary finite structures, so there's some conversion there too. Then you have to prove that all the stuff you did is in fact correct. All in all, it's not pretty.

So i have to ask: Is there any proof of this result that isn't afraid of working out some of the details, but has the same intuitive clarity as the usual short proof?


texts: How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

texts:
In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which are productions annotated with a position and a lookahead character.

It's known that given a state in an LR(1) automaton, the configurating set formed by dropping the lookahead tokens from each LR(1) item yields a configurating set corresponding to some state in the LR(0) automaton. In that sense, the main difference between an LR(1) automaton and an LR(0) automaton is that the LR(1) automaton has more copies of the states in the LR(0) automaton, each of which is annotated with lookahead information. For this reason, LR(1) automata for a given CFG are typically larger than the corresponding LR(0) parser for that CFG.

My question is how much larger the LR(1) automaton can be. If there are $n$ distinct terminal symbols in the alphabet of the grammar, then in principle we might need to replicate each state in the LR(0) automaton at least once per subset of those $n$ distinct terminal symbols, potentially leading to an LR(1) automaton that's $2^n$ times larger than the original LR(0) automaton. Given that each individual item in the LR(0) automaton consists of a set of different LR(0) items, we may get an even larger blowup.

That said, I can't seem to find a way to construct a family of grammars for which the LR(1) automaton is significantly larger than the corresponding LR(0) automaton. Everything I've tried has led to a modest increase in size (usually around 2-4x), but I can't seem to find a pattern that leads to a large blowup.

Are there known families of context-free grammars whose LR(1) automata are exponentially larger than the corresponding LR(0) automata? Or is it known that in the worst case, you can't actually get an exponential blowup?

Thanks!


texts:
In his networking textbook, the world-renowned computer science expert Tanenbaum says that e-mail communication is inherently peer-to-peer. Here is the paragraph from the book:

Peer-to-peer communication is often used to share music and videos. It
really hit the big time around 2000 with a music sharing service
called Napster that was shut down after what was probably the biggest
copyright infringement case in all of recorded history (Lam and Tan,
2001; and Macedonia, 2000). Legal applications for peer-to-peer
communication also exist. These include fans sharing public domain
music, families sharing photos and movies, and users downloading
public software packages. In fact, one of the most popular Internet
applications of all, email, is inherently peer-to-peer. This form of
communication is likely to grow considerably in the future.

I have come across several people claiming the opposite - e-mail is not peer-to-peer. They say that there is no direct connection between peers. Also, one of their argument was that if you bring one of the servers down, e-mail won't work anymore. However, logically, if Alice sends an e-mail to Bob, in my eyes, Alice and Bob are peers. Just as with regular (snail) mail, anybody can send an e-mail message to anybody. There is no distinction between clients and servers. Hence, logically, a simple two-party e-mail message is a message between two peers. The route the message traverses is irrelevant.
So, is e-mail peer-to-peer? If not, what did Tanenbaum mean by saying that?


texts: Proving that a derived language is regular

texts:
Suppose I have a DFA recognizing a regular language $L$, how do I prove that
$$\text{lefthalf}(L)= \{ w_1 \mid \exists w_2 \in \Sigma^* ,w_1w_2 \in L \land \|w_1\| = \|w_2\| \}$$ is also a regular language?


texts: Multiple parameter predicates and the Relational Model

texts:
I've got a very general question about the relational model and it's relationship to 1st order predicate calculus. It will probably seem very basic to most, I'm afraid, a consequence of me grappling with these concepts on my own for the first time. I would love it if someone could please clarify.
One often sees examples of the predicate calculus of the form: P(x,y,z) where P is a predicate with multiple parameters, interpreted for example as "Gary thinks Jimmy likes Kate", with all the arguments coming from a single domain such as "people in my Painting class" or similar. Sometimes you see the results in tabular form with the comment "and this is actually a simple database" or similar. And then you find descriptions of the Relational Algebra (apparently equivalent to the predicate calculus) that define a relation as a subset of the Cartesian Product of however many domains as attributes and creating a tuple accordingly. Fine, no problem with those descriptions in isolation.
But it seems to me that in the relational case, you have a domain (=type) per attribute, but in the Predicate Calculus example above you only have one domain. Further, the expressions seem to be of a different kind altogether. The Relation seems to group the attributes in such a way that they are totally independent of each other, an arbitrary collection of independent facts about each element, that is true by virtue of being present as a tuple in the relation. Whereas in the logic example, the parameters do NOT seem to be independent in the same way- for example the argument order is critical to the interpretation of the resulting proposition. I can't figure out what I'm missing!
It occurs to me that perhaps to say that for the Predicate example ("Gary thinks Jimmy likes Kate"- call it P) that all the arguments come from a single domain is really just shorthand for saying that it is a Cartesion Product of the same domain ("people in my logic class"- call it D), so that the real and proper description of the domain for P is D x D x D. Would that get us out of trouble? I hope somebody can understand my confusion and help an amateur out!


texts: How on-chip multithreading prevents cache misses from stalling a processor pipeline?

texts:
On-chip multithreading is considered a powerful performance enhancer technique that enables a processor to handle multiple threads at the same time. If I got the idea right, multithreading avoids pipeline stalls by processing instructions coming from different threads - since no data dependencies exist between different threads (in the textbooks, synchronization points are dropped for convenience), pipelines will never stall.
However, authors like Tannenbaum state things like that (Structured Computer Organization, 6th Edition, page 562):

  "... when a memory reference misses the level 1 and level 2 caches,
  there is a long wait until the requested word (and its associated
  cache line) are loaded into the cache, so the pipeline stalls. One
  approach to dealing with this situation, called on-chip
  multithreading, allows the CPU to manage multiple threads of control
  at the same time in an attempt to mask these stalls. In short, if
  thread 1 is blocked, the CPU still has a chance of running thread 2 in
  order to keep the hardware fully occupied."

I do understand that a pipeline will never stall if the data dependencies of subsequent instructions are eliminated (that is what out-of-order execution does), but if a memory reference is made by an instruction, the pipeline has to stall until the necessary information is retrieved for the main memory. I mean, no further instructions can be processed until the memory is read and the associated word is loaded. However, Tannenbaum and other authors suggest the opposite: while the word in question is being retrieved, additional instructions from other threads can be issued and that makes no sense to me. Can you folks clarify that? Shouldn't memory accesses prevent the pipeline from accepting new instructions, regardless the thread they come from? Thank you!


texts:
I studied methods for inserting new nodes into Red-black trees for the first time this month.

In doing so, I read a lot of pages on the internet and found that ( if I'm not mistaken ) there are many, many, many accepted algorithms for inserting nodes into red-black trees.

Furthermore, I noticed that it is possible to have two insertion algorithms that don't break red-black tree invariants, but also can start with the same initial tree, insert the same node, and end up with different resulting trees.

I think.

For example, take this website's algorithm for insertion:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

And then there's this famous example from 'Purely Functional Data Structures' by Chris Okasaki:

And then there's this algorithm from Ohio State:
https://www.pdf-archive.com/2017/03/28/08-red-black-tree/08-red-black-tree.pdf

Is it true that there are many red-black tree insertion algorithms that, given the same domain, will map the elements in that domain differently?


texts: What is the name of the variant of ICP where the correspondence of the points are known?

texts:
Traditional ICP assumes that the inputs are point clouds with no predefined correspondences between the clouds.

If I know before hand that some / all points in one point cloud corresponds to some / all points in the other point cloud, I assume this becomes an easier problem to solve.

What is the name of this modified version of point set registration and what are some algorithms that solves this?


texts: Grammar for all words other than $wq,qw$

texts:
I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\{m ∈ \{q,w\}^* \mid m \neq wq,qw \}$.
My grammar:
\begin{align}
&S \to qSw \mid wSq \mid qXq \mid wXw\\
&S \to qYw \mid wYq \mid q \mid w\\
&X \to qX \mid wX  \mid qXw \mid wXq \mid ε \\
&Y \to qw \mid wq \\
\end{align}


texts: Given a language L, I've shown that L is not regular. Can I conclude that it is not decidable or are there non-regular languages that are decidable?


texts:
Can somebody define what is a fuzzy lattice? How to compute lattice of a fuzzy number?

Please try to be generic and basic in the explanation as I'm a beginner in studying fuzzy theory and soft computing.


texts: Trouble understanding theory for error detection and correction in repetition code

texts:
Question 1

Consider a repetition code to detect $m$ errors. What is the smallest repetition parameter $k$ (i.e., the number of repetitions per bit) it should be used so that the code can always detect $m$ errors?

To be clear I know that you need $k=2m+1$ to correct errors, I am asking what is $k$ if you only want to detect errors.
I know the answer is $m+1$.

I read some articles about Hamming codes but I didn't understand the explanation.
I also read this post but it wasn't helpful enough:
Hamming distance required for error detection and correction

Question 2

Let a code make 3 repetitions and add a parity bit to the message. For example, $1010$ is encoded as $111 \; 000 \; 111 \; 000 \; 0$.
How many (maximum) errors can this code identify?
How many can it fix?

(The answer is fix one and identify three but I don't understand why.)


texts:
I have no cs background (algorithm and data structure), but need to find a data analysis related job since my major is math / statistics. However, (I am trying to avoid software engineering related jobs) no matter which position I applied, from finance to bioinformatics, almost every technical interview involves hash table. I feel very frustrated that if I don't know this, I cannot find a job. If I know this, then I have to study algorithm and data structure (then solve all the problems in Leetcode, etc), which is equivalent to a SDE job seeker .

For example, I got an interview question: $a=(3,2,5,6,1,3,2)$, $b=(4,3,6,2,3)$ ( generally, length of $a$ is N, length of $b$ is N). And there is a program to output all matched pairs (just a pseudocode in whatever language):

for i in 1:N
   for j in 1:M
       if a[i]=b[j]:
         print(a[i])

Then the program outputs $(3,3,2,6,3,3,2)$. The time complexity of this is $O(MN)$, and the interview question I did not figured out is, to get the same output, how to improve this program?

They finally told me that it takes $O(N)$ to make a hash table (search table) for $b$, and then use $O(M)$ time to loop $a$. So the total time is $O(M+N)$.

My question is: is this just that simple? (they said they do not care space complexity at the beginning)

I know nothing about hash table except the only fact that it takes $O(1)$ to search the keyword. So assume this is true, I can understand his answer. However, I am just curious, is this just this simple? I mean, it seems there is no algorithm in this solution but just "hash it". Are all the core intelligence to solve this problem is hidden in the hash table property and how hash table is created in $O(N)$? Is this a usual way for a cs student/SDEer, who knows hash, to solve this problem, that comes first in their mind? (To me, I think his example code is exactly what I will write if I meet this problem in my research work.)

If it is so straightforward to think in this hash way for those know hash, then I think I should also learn algorithm and data structure. Otherwise I think I won't get a job. Is there any suggested book or tutorial that can help me to solve this kind of problem algorithmly or hashly?


texts:
I've been studying some number theory, and I came across this problem:

  Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.

  Consider the following algorithm to choose a random n-bit prime:

  1) Pick a random n-bit number $k$.

  2) Run a primality test on $k.$

  3) If it passes the test, output $k$; else repeat the process.

  Show that this algorithm will sample on average $O(n)$ random numbers before hitting a prime.

I'm guessing I need to approach this probabilistically. Let $p$ be the probability that we randomly choose a prime. Let $E$ be the expected number of random numbers to choose before hitting a prime. Then, I need to express $E$ in terms of $p$, and show that it is less than or equal to $n$, right? Since, if we sample on average $O(n)$ numbers, then the expectation $E$ should be $\le n$.

But I'm a bit stuck on how to go about doing this. Is each event of choosing a random number binomial? Either we choose a prime or we don't, and each event is independent. But the expectation of a binomial RV is $np$, which is clearly not $\le n$.

I feel like I'm going about this all wrong. What am I missing here? Am I even on the right track? Thanks for your help.


texts: Can synchronous data transfer be used for transferring large data in case of computer architecture and organization?

texts:
I am learning computer architecture and organization.

I have this confusion, can synchronous data transfer be used for transferring large data in case of computer architecture and organization?

I have read that synchronous data transfer can be used for transferring large data but I think it is true only in case of computer networks, in case of computer architecture and organization I think DMA is used for transferring large data. So if someone asks me if synchronous data transfer be used for transferring large data in case of computer architecture and organization. Should I say yes or no?


texts: A flawed theorem about regular languages

texts:
I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem:

The language $\{awwa \mid w \in \{a,b\}^* \}$ is regular.

Well, that part is obvious, we can prove that the language is not regular using the pumping lemma.
The question I am asked is to find the flaw in the "proof" for this theorem:

Let
$\qquad L_1 = \{ aw \mid w \in \{a,b\}^* \}$
$\qquad L_1^R = \{ wa \mid w \in \{a,b\}^* \}$
Let $L_2 = L_1 L_1^R = \{ awwa \mid w \in \{a,b\}^*\}$ be even-length palindromes that begin and end with an $a$.
Since $L_1$ is regular, and the class of regular languages is closed under reversal and concatenation, we conclude $L_2$ is also regular.

Can you find the flaw? I could build a DFA for $L_1$ and $L_1^R$, so I know they are regular. And regular languages are closed under reversal and concatenation.
But, however, $L_2$ is still not regular, so where is the mistake in the "proof"?


texts: Parallel deletion and traversal in a lock free linked list

texts:
I'm unsure about the safety of deletion in a linked list. I've seen the issue posed by a parallel insertion and deletion (resulting in the loss of the insertion) and proposed solutions to that problem. That makes perfect sense. However, nowhere have I seen it mentioned that an unlucky traversal in parallel with a deletion can cause problems. For example, if we have the linked list:

A -----> B -----> C* ------> D

and one process (process 1) is traversing it, currently pointing at C (as indicated by the *), however before process 1 reads the next pointer of C, another process (process 2) deletes C and frees its memory. Then, when the process 1 attempts to read C's next pointer, it will be reading uninitialized memory (which could be used to store an int for example), and thus could be pointed to an invalid location, and cause a segmentation fault by dereferencing that pointer.

How can this issue be avoided?


texts: Is there a more commonly-used term for "multi-pivoting"?

texts:
Consider the following computational problem (or rather, task):

  Given:

  An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain
  An ordered sequence pivot values $p_1 \ldots p_m$ (i.e. such that $i < j \implies p_i < p_j$).

  Output:

  A partition of $A$ into $m+1$ parts (be they sets or shorter arrays),
  denoted $A'_0 \ldots A'_m$ , such that if $i < j$ and $x \in A'_i$
  then $x < p_j$.

One could call this computing a "histogram with variable-size bins", or "m-pivoting", or "m-way ordered partitioning", etc.

But are there names for this task which are more commonly used than others?

PS - If it helps, we can relax the requirement on the pivots to $p_i \leq p_j$.


texts: What's the polynomial involved in the PCP theorem?

texts: Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?


texts: What is the point of traversing a binary tree in preoder, inorder or postorder?

texts: Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?


texts: Count total number of k length paths in a tree

texts:
This is a question from a competitive programming competition.
Given a tree with n nodes and a number k, find the total number of paths of length k in that tree.

I know for a fact that a solution can be found by using a centroid decomposition, however I am simply not sure on the exact relationship between the original tree and the tree we got from decomposition other than the fact that the length of path A -> B in the original tree can be decomposed into a sum  A -> C + C -> B in the decomposed tree. Where C is the LCA(A, B). All distances being in the original tree.


texts:
We know that $NC^1 \subseteq NL \subseteq AC^1$ and that 2-SAT is complete for $NL$.

  How does one construct an $AC^1$ circuit for 2-SAT?

Recall that $AC^1$ circuits have $O(\log n)$ depth where $n$ is the number of bits in the input.

I have read Herbert Vollmer's book on Circuit Complexity as well as the chapter in Arora-Barak's book.  Still, appears to be very challenging.

For example, we can fix the length of the input for each variable (say $3$ bits).    For each literal, let the first bit indicate whether it is positive or negative.  So each literal is represented by $1+3 = 4$ bits.

Thus the negative literal $\neg x_1 \equiv 0001$ and the positive literal $x_2 \equiv 1010$.

Let FALSE $\equiv 0000$ and let a unit clause (a clause with one literal) ($x_i$) be represented as $(x_i \lor FALSE)$.

Hence a 2SAT formula $\phi = (x_1 \lor \neg x_2) \land (x_5 \lor \neg x_6)$ would be represented as

$11110$-$1001$-$0010$-$1101$-$0110~ $ as input to the circuit
(dashes just added for reading clarity only).

The first $4$ bits $1111$ mean that each literal is represented by $4$ bits --- the fifth bit ($0$) is just a separator before the actual input $\phi$ begins.

And then we have to implement an algorithm in the (C $\log n$) levels above the input level, for some constant $C$, using $AND$, $OR$ and $NOT$ gates, allowing unbounded fan-in.

Is this going in the right direction?


texts: Firefly algorithm number of objective function calls

texts:
Reading an article (arXiv) about the Firefly optimization algorithm, it is stated that the objective function is called only once per firefly per iteration, but following both the pseudo-code in the article and some implementations I found online I do not understand why this is the case..

As I understand the following holds:

The objective function is called whenever we want to update the light intensity $I_i$ of firefly $i$
In a given iteration and firefly $i$, for every firefly $j$, if $I_j>I_i$ we move firefly $i$ and immediately re-calculate the intensity.

From this, if the fireflies' intensities are ordered as $1,2,3,\dots,n$, and the updated intensity increases by each movement are small (i.e. each movement will increase the intensity by at most 1), in one iteration the first firefly will move $n-1$ times, the second $n-2$ times,... each movement calling the objective function for a total of $n(n-1)/2$ calls. Where does the figure of $n$ objective calls per iteration comes form?


texts:
How can we construct an algorithm which finds $\mu$ that minimizes $\max | x_i - \mu |$ in a linear time for an array of numbers $[x_1, x_2, \ldots, x_n]$?

I take $g = \max_{i\in \{1,\ldots,n \} } x_i$ and $l = \min_{i\in \{1,\ldots,n \} } x_i$, and $\mu = l + \frac{(g - l)}{2}$

Is it true and why it minimizes the function?


texts: What use does the predictor stage in a particle filter have?

texts:
Im a bit confused about the particle filter.
I understand the generic particle filter algorithm but in some literature say particle filter has predictor stage which is not mentioned in the generic particle filter.

I thought it weighed the particle based on observation. What's the predictor stage used for?


texts: Train Neural network with infinite amount of data

texts:
Does a sufficiently complex neural network guarantee to find the optimal solution, given an infinite amount of data and the back propagation technique for training?

In other words, given an infinite amount of training data, can neural network get out of local minima and approaches optimal state?

The question is purely theoretical.

Update:
It is obvious that a proper neural net with optimal set of weights (in some occasions num of neurons should go to infinity though) can approximate any well-defined function. However, in practice we do not have that optimal set of weights. Those weights are approximated by a training method of choice. The most commonly used method is back-propagation. Now the question was when the number of training samples grows, does the neural net converge to the Bayes rule?  In other words, is it a universally consistent classifier? the answer seems to be no. When it gets stuck in local minima no matter how much you increase the training set, it will never get out of it (when using BP as a training method).

you may wanna look at this paper: , (Farago,93)"strong universal consistency of neural network classifiers"

Update2: Perhaps, my update was not clear since I keep getting wikipedia pages as answer: Hope this one finally clarifies:

As I said in my original question, stochastic gradient descent (or perhaps other more complex choices) with back-propagation is going to be used to train the network. This means the weights are not optimal (optimality in the sense that the network may not obtain the Bayes err rate). We also have infinite amount of data which translates to learning in the limit or online learning framework. But to keep it simple, instead of having infinite amount of data, we may assume we have finite but arbitrary large set of data.

The question is, whether the performance of a neural network in theory can now converge to Bayes rate? using any known regularization method such as dropout (which somehow is equivalent to bagging), varying the network structure during training (adding or removing layers, increasing the number of neurons etc), early-stopping and any meta algorithm to sample from this large data-set, or anything else you can think of, are allowed.

PS: Many learning methods are universally consistent meaning that as the number of training samples grows, they guarantee to converge to something good (usually Bayes rate or $\epsilon$ neighborhood of it). I am surprised if we don't have any interesting theorem in that respect for Neural Networks.


texts: Prove DFA constructed by subset construction has exactly the states and transitions of NFA plus transitions to new dead state

texts:
Prompt: if $N$ is NFA that has at most one choice of state for any state and input symbol, then the DFA constructed from $N$ by subset construction has exactly the state and transitions of $N$ plus transitions to new dead state whenever $N$ is missing transition for given state and input symbol. Prove this contention.

I get this intuitively and I wrote out a proof, but I think it may not be formal enough to be an actual proof.

Prove that DFA has all the same states of $N$ plus a new dead state

$\delta(q,a)$ never has size greater than one. This means on reading input symbol $a$ from a state $q \in Q$, the DFA transitions to a single state or it dies. In other words, $\delta_N(q,x) = \{p_1\} | \emptyset$, where $q, p_1 \in Q_N$ This means $Q_N$ consists of singleton states.

Subset construction gives us $Q_D$ as states of DFA constructed from N, which is equal to $P(Q_N)$. However, as $\delta(q,a)$ never has size greater than one - or it only goes to a single state or it dies - the only subsets $S$ of $Q_N$ accessible by the DFA are the singleton states of $P(Q_N)$, which is also equal to $Q_N$. In this way, $Q_D = Q_N + z$, where $z$ is new dead state.

Prove that DFA has all same transitions of N plus transitions to dead state whenever N is missing transition for given state and input symbol

Subset construction tells us that

for each set $S \subseteq Q_N$

$\delta_D(S,a) = \cup_{i}^{k} \delta_N(p,a)$

Pt.1 showed that $S = \{p\}$, so we don't need to take the union of each $p$ in $S$ because there is only one state.Therefore we can say
$$\delta_D({p}, a) = \delta_N(p,a)$$

In the case then that $\delta_N(p,a) = \emptyset$, then we add a transition to the new dead state.  Therefore the union of all the transitions of the DFA equals the union of all the transitions of $N$ plus the new transitions to the dead state.


texts: What are elementary operations in time complexity definition?

texts:
Wikipedia gives us the following defintion of time complexity:

  "In computer science, the time complexity is the computational
  complexity that describes the amount of time it takes to run an
  algorithm. Time complexity is commonly estimated by counting the
  number of elementary operations performed by the algorithm, supposing
  that each elementary operation takes a fixed amount of time to
  perform."

Now what are these elementary operations ? Are they arithmetic operations or some simpler operations ?
Thanks in advance!


texts: How can I build a fool proof security system?

texts:
From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not.

That tasks looks very similar to me than deciding a non-trivial property of an arbitrary large set of programs. And as we know by Rice or diagonalization or many different methods, this problem is undecidable.

That means (if I am not wrong) that for some input D might run forever without sending a reply. Obviously that's not acceptable for a security system. Let's assume for sake of simplicity, that I need a guaranteed YES or a NO.

How can that be implemented in reality? And what are the consequences for the results?


texts: What does machine code actually look like while being run?

texts:
When machine code is actually being executed by hardware and the CPU, what does it look like?

Would it look like binary, as in instructions being represented by ones and zeros, or would it be something made up of hexadecimal digits where opcodes are bytes presented as hex numbers which can be broken back down into binary numbers, like bytecode?


texts: Tracing a polynomial algorithm for the problem of maximum-weight independent set

texts:
It should be a very easy question, but I am a little bit confused.
According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using Dynamic Programming (the Algorithm is also explained on page 562 of the book Algorithm Design). Now, imagine that we want to trace the algorithm on a random graph like the figure below where the numbers in the balls show the weight.

I want to know, does it matter which node I am selecting as the root?
Can you please guide me through the steps of this algorithm's tracing on this graph?


texts: I am having trouble understanding (and implementing) logistic regression for classifying into three classes

texts:
(For reference, i am using Kevin P Murphy's Book "Machine Learning: A Probabilistic Perspective" and implementing with MATLAN - without any toolboxes)

I have a dataset with 392 samples (rows), each sample has 8 features (columns), one of which defines the class (i.e. column 1 of features is divided into three equal bins which define the three classes - low, medium, and high).

I am having a really hard time understanding how to create a logistic regression model to classify a sample into one of these three classes.

I just finished learning and making a linear regression model where I learned about both the Ordinary Least Squares (Closed form) solution for the weight vector, and also Gradient Descent (Open Form) solution. But i never implemented gradient descent because my data was fitted perfectly fine with the OLS solution for weight vector.

I am extremely confused how to create a weight vector for Logistic regression, I understand that it requires use of Gradient Descent because there is no closed form solution. I also read about the Newton method for calculating the weights but I don't understand it at all.

And after you use these methods to calculate weights how do you apply the weights to the sample data? In Linear regression it was simply because you simply multiplied the weights by the features (and higher order features for higher order linear regression), but is it the same in logistic regression?

Moreover my understanding so far is that this model only works for binary classification, so how would i do it for three classes?

Basically my question boils down to this:

How exactly do you find the weight vector for logistic regression (using either gradient descent or newtons method, whichever is easier) and how do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two).


texts:
This question might sound stupid but, can the language of a TM be not recursively enumerable ?

Thank you ~


texts: Is maximum edge-weighted triangle-free graph NP-hard?

texts:
Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$.

Is this problem NP-hard? I thought I saw some mention or folk-theorems that it was, but I can't find anything. There is a similar problem which is known to be NP-hard:

Given a graph $G$ with weights $w_v$ on the vertices, choose a subset $S$ of the ''vertices'' such that the induced subgraph $G_S$ doesn't contain any 3-cycles, maximizing $\sum_{v\in S} w_v$.

There are many sources online talking about how MAX-IND-SET can be reduced to this. It's not immediately obvious to me if this generalizes to the above, though. The closest thing I did find was https://www.sciencedirect.com/science/article/pii/S0166218X14002182 which mentions that finding maximum-cardinality triangle-free 2-matchings (so that $S$ has max degree 2) is easy, and it seemed to suggest that it would work for the weighted version as well, although I didn't quite follow it all the way through.

Anyone have a reference for this, or want to provide a reduction? :)


texts: Choose minimum subset of edges in tree that connects all important nodes

texts:
Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$.

We want to choose subset of edges of the tree such that:

For each two important nodes at least one edge of the path between them will be choosen
The sum of the subset of edges will be minimized

Note that we only need to find the sum of the edges in the subset, not the edges in the subset.

For example if we have the tree with the edges $(1, 2) \text{ weight = 3}, (1,3) \text{ weight = 10}$ And our important nodes are: $2, 3$. We should chose only the edge $(1,2)$


texts: sequence of problems that take $\Theta(n^k)$ for increasing $k$?

texts:
Do we know an infinite sequence of decision problems where the most efficient algorithm for each problem takes $\Theta(n^k)$ time, where $k$ increases unboundedly?

Suppose for example that we would know that finding a k-clique takes $\Theta(n^k)$, then this sequence could be {1-clique, 2-clique, 3-clique, ...}. However, perhaps there are more efficient algorithms for k-clique, so this answer is incorrect.

EDIT:

By the Time Hierarchy Theorem (which includes "P does not collapse to DTIME($n^k$) for any fixed $k$"), such a sequence should exist.
After some discussions in the comments, common NP problems are not good candidates. If it takes only $O(n)$ time to check a certificate (or $O(n^c)$, where $c$ is a constant independent of $k$), it would imply that $P\neq NP$


texts: Significance of parameters in Tiny Mersenne Twister algorithm

texts:
I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned integers "mat1", "mat2", "tmat", and an array called "status" which is four 32-bit unsigned integers wide.

I am relatively new to the subject of random number generation; however, I have been able to teach myself a lot about the subject over the past couple of weeks. I know what the purpose of a seed is, different methods such as linear congruent, LSFR, GFSR, etc. So I've been doing my "homework" and researching the topic to the best of my ability (contrary to what the guys at Stack Overflow think). Unfortunately, the Mersenne Twister in general is extremely poorly documented and very few documents exist to explain the code and math side-by-side. The TinyMT's documentation is even worse, it's virtually non-existent! So developing accurate Doxygen comments for this part of the API is going to be tricky.

With that said, hopefully somebody more qualified than I can help me out here. What is the significance of the aforementioned parameters? What do they do, what do they mean, what do they stand for, etc? My guess would be as follows:

mat1 - Matrix 1
mat2 - Matrix 2
tmat - Tempering Matrix
status - 127 bit wide "seed" (where the last bit goes, I'm not sure)

Given that the user provides values for "mat1", "mat2", and "tmat," are there any precautions they need to take before supplying values for them? Again, this is for an API and its documentation, so I would like to be able to give the customers a good idea of what they need to use the RNG and hopefully make the lives of other fellow programmers easier. Thanks!


texts: Applications of algorithms to stock trading analysis

texts:
There is a new Quantitative Finance SE site. However, I am interested in asking the "CS crowd":

  What are some interesting key references or surveys on applying algorithms to stock trading analysis?

There are many such references, however, I am particularly interested in those that would appeal to those with a CS background. Further, I am especially interested in those that find surprising applications of TCS or mathematics theory.


texts: Complexity of a graph parity-coloring problem

texts:
Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white.  I'm curious about the complexity of the following problem:

Find a subset $S$ of edges of G of maximal weight, subject to the constraint that any node colored black is incident to an odd number of edges in $S$, and any node colored white is incident to an even number of edges in $S$.  The constraint is sort of a $2$-coloring up to parity.

The problem seems hard in general.  I'm more interested in the simpler case that $G$ is a tree.  In this case, are there any efficient algorithms to determine such a set $S$?  Also, does this problem have a name?


texts: Commonly-used formal definition of graphs with 'connections'?

texts:
Sometime you want to model some data from the real world using a graph, but such that edges don't just connect to a vertex; rather, they connect to some aspect of that vertex - some connection if you will.

For example, a node in a family tree would be a person, and they have a mother and father (never mind about adoptions etc.). Now, when you connect one of the parents to the child you want to connect it as "the father" or "the mother"; so a "connections graph" model for this tree would see each vertex have a set of 3 possible connections: "father, mother, child" (with the child being used to connect it to its biological children's nodes).

It's true that you can always get around really needing connections, e.g. with gadgets in their stead (say, each connection has a gadget vertex, so an original vertex is now surrounded by its connections as satellites and edges only exist between these satellites). But I'm interested in dealing with such connections explicitly.

So, connections can be represented by a set; or as an ordered sequence (perhaps even always $0...\Delta$ with $\Delta$ being the maximum degree of the graph); or the edge set could incorporate the connections apriori, i.e. an endpoint could always be a tuple of a vertex and something else. And the connection set might be shared, or per-vertex; and so on.

My question is: What are some specific formalizations of this concept which are used often (if there are such at all)?

Notes:

I don't care whether it's a directed graph or not, you can always switch from directed to undirected and back in a relatively straightforward way.
Here's a diagram of one of these:

digraph G {
rankdir="LR";
    a->b [taillabel="x"; headlabel="y"]
    b->c [taillabel="z"; headlabel="w"]
}


texts: Job Scheduling with deadline with $nlogn$ algorithm

texts:
We know that there is a Greedy algorithm for scheduling of $n$ jobs which each job has its own deadline and profit.

In greedy algorithm, we sort the set by their profit descendant, And if a job can add to a possible set of jobs, we add it to the set.

A job can be added to the set, if it starts before its deadline and each work need 1 time slot for doing.

Is there any $O(nlogn)$ algorithm for this problem as follows?

Sorting the set by their profit using merge sort in $O(nlogn)$
Add the first job to the possibility set.
For remain jobs, add the job to the set of its deadline is less than its index in possibility set.
We have to remain the possible set sorted. Then for each new coming job, we can add it to the set using binary search in $O(logn)$

Total cost of the above algorithm is $O(nlogn)+O(n)*O(logn)=O(nlogn)$

Is this algorithm correct?


texts:
I have a recurrece equation

Changed notations:
$\qquad\displaystyle G(W) = \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$,

I am not sure if I understand $\ w_i $ correctly.

On each iteration my $ w_i \leq W $ . So my $ w_i $ will be previous $ W-s_i $ since G takes one argument?


texts:
Given Array $A$ of size $n$ that contains all the integer values $[0,n]$ except one.

In this question we assume that the time we need to check one bit $j$ in number $A[i]$ is $O(1)$,and to check the number $A[i]$ is $O(\log n)$.

Find an algorithm that finds the missing number in $O(n)$.

So creating a trivial counter array and searching for a 0 count wouldn't help - it would be $O(\log n)$.

I also thought about counting the bits and finding the missing one, but that wouldn't help either.


texts: Add capacity to the uni-weighted graph to increase max flow

texts:
Given a uni-weighted graph G (in which each edge has the capacity of 1), and we have k extra capacities (k is an integer) that we can spend on any subset of existing edges. That is, we can increase the capacity of any existing edges but all increases should sum up to k.
How to improve the max (s,t) flow as much as possible?

I'm considering the residual graph but it seems not that easy.
I also thought the corresponding edge-disjoint paths from s to t, however they will change after adding the capacity.


texts: NFA to accept strings where the third AND the third-last element are b

texts: Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I don't know where to start. Help please.


texts:
I am confused about the definition of sub graph isomorphism, wikipedia says that the subgraph isomorphism problem is a computational task in which two graphs $G$ and $H$ are given as input, and one must determine whether $G$ contains a subgraph that is isomorphic to $H$.

Is this the correct statement or is it whether $G$ contains a subgraph that is isomorphic to a subgraph in $H$?


texts: Parsing a context free grammar, Backus Naur question

texts:
Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of symbols?  For example the BNF grammar:
<r0> ::= <opt-whitespace> "a" <opt-whitespace> "b" <opt-whitespace>
<opt-whitespace> ::= " " <opt-whitespace> | ""

How is the $\epsilon$ read during creation of a parse tree for string in the language?  From what I observe, when the parser is recursing <opt-whitespace> for each next symbol of input, eventually "a" will be read which is not in the rules for <opt-whitespace> and the string will not be recognized.
I understand the use of $\epsilon$ when using the grammatical rules to generate the strings of the language, however it causes confusion when I think of how to parse the input.


texts: How to shift a matrix by x rows and y columns in the most efficient way?

texts:
My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner.

x and y could be negative or positive. Negative would mean up/left and positive would mean down/right.

My current solution is something like this:

def rotate_columns(col, y):
    new_col_position = col+y if y < 0 else (col+n-y)
    return new_col_position
def rotate_rows(row, x):
    new_row_position = row+x if x < 0 else (row+m-x)
    return new_row_position

def shift(x,y):
    N = M.copy()
    for col in range(n):
new_col_position = rotate_columns(col)
        for row in range(m):
            N[row][new_col_position] = M[row][col]
    for row in range(m):
        new_row_position = rotate_rows(row)
        for col in range(n):
            N[new_row_position][col] = M[row][col]

An example:
Say, a given matrix is:

1 2 3
4 5 6
7 8 9

with x = 2, y = 1, it would be:

6 4 5
9 7 8
3 1 2

Is there a better way to solve this? By better, I mean better time complexity.


texts: No FSM/Regex exists for this language right?

texts:
The language is this:

$L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$

This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, right?


texts:
I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in real life, it is very easy to construct an oracle $O$ such that $\mathbf{P}^O \neq \mathbf{BPP}^O$. Frankly I don't find this easy at all. Even more so I find it implausible sounding. I will explain my reasoning here.

My understanding from earlier parts of the book is that the reason people believe that $\mathbf{P} = \mathbf{BPP}$ is that we believe in the existence of good pseudo-random generators (i.e. deterministic processes that generate random looking strings) and even have some plausible looking candidate pseudo-random generators. Now whenever we want to run a $\mathbf{BPP}$ algorithm on a $\mathbf{P}$-machine we just run the algorithm as written, but replace every random bit the $\mathbf{BPP}$-machine would use by a pseudo-random bit generated by our pseudo-random generator.

You can see my problem now: we can just apply the same strategy in presence of the oracle. Whenever the $\mathbf{BPP}^O$-algorithm makes an 'ordinary' deterministic step we do the same thing in our $\mathbf{P}^O$ algorithm. Whenever the $\mathbf{BPP}^O$-algorithm queries the oracle, we query the same oracle in our $\mathbf{P}^O$ algorithm and whenever the $\mathbf{BPP}^O$-algorithm uses a random bit we use a bit from our pseudo-randomgenarator. What could go wrong, short of the oracle magically coming to life, taking physical form and smashing our pseudo-random generator with an axe? So my question is:

  What is an example of an oracle $O$ such that $\mathbf{BPP}^O \neq \mathbf{P}^O$ and what problem is in the former but not the latter class?

Update: while typing a link to the following question showed up that is essentially asking the same: Existence of suitable pseudo-random number generators to derandomize BPP to P

However I don't see how the accepted answer answers my question. It seems to say that there are oracles that can distinguish the output of a given pseudo-random-generator from actually random data but

a) I can't think of a problem where having access to truly random data would give an advantage over having access to only outputs of $G$ to solve it and

b) What if the $\mathbf{P}$-machine fools the oracle by using a PRG other than $G$?


texts: Reduction Vertex cover into Dominating Set

texts:
I have a question to the reduction from Vertex Cover into Dominating Set.

So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new graph $G'$ which has the same vertices of G, except the isolated ones. For each edge $\{u,v\}$ in $G$, we add a new vertex that is connected with $u,v$.

So my question is, why I have to form every edge into triangles? Why is it not enough to only remove the isolated vertices?

Every vertex cover without isloated vertices is a dominating set at the same time


texts: Solving functional equations for unknown functions in lambda calculus

texts:
Are there any techniques for solving functional equations for unknown functions in lambda calculus?

Suppose I have the identity function defined extensionally as such:

$I x = x$

(that is, by writing down an equation for the expected behaviour of that function) and now I want to solve it for $I$ by doing some algebraical transformation to get the intensional formula for that function:

$I = \lambda x.x$

that tells how exactly does the function do what was expected (that is, how to implement it in lambda calculus).

Of course the identity function is used just as an example. I'm interested in more general methods of solving such equations. In particular, I would like to find a function $B$ that satisfies the following requirement:

$B\;f\;(\lambda x.M) = (\lambda x.f M)$

that is, "injects" the given function $f$ into  the given lambda function $(\lambda x.M)$ before its "body" $M$ (which is some arbitrary lambda expression), possibly by taking it apart and constructing a new one, so that it became a parameter the function $f$ is applied to.


texts: Is it possible to prove closure of decidable languages under union and intersection, using enumerators?

texts:
We can use multi-tape enumerators.
(Of course it is not valid to use turing machines albeit the fact that any enumerator has an equivalent TM)

What we need is to prove that if $A$ and $B$ are decidable then $A\cup B$ and $A\cap B$ are also decidable.

Can it be done? If so, what is a possible approach?


texts: Can there be a language not Context free but still PDA acceptable?

texts:
Let the input alphabet be $Σ = \{1,x,=\}$
Let the stack alphabet be $\tau = \{1,\$\}$ where $\$$ is the initial stack symbol.

Let,$q_0$ be the initial state of the PDA,$q_f$ be the final state of PDA,
I can define a transition function for PDA like this.

$(q_0,1,\$)\rightarrow(\$1,q_1)$
$(q_1,1,1)\rightarrow(1,q_1)$
$(q_1,x,1)\rightarrow(1,q_2)$
$(q_2,1,1)\rightarrow(1,q_2)$
$(q_2,=,1)\rightarrow(1,q_3)$
$(q_3,1,1)\rightarrow(\epsilon,q_3)$
$(q_3,\epsilon,\$)\rightarrow(\$,q_f)$

Now the PDA can recognize language $L = \{1^m x 1^n = 1^{mn}\}$
But According to https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/18/Small18.pdf Slide 24 this language is not Context Free.

Assume that I am quite beginner in TOC.


texts: Anotation rules for while rule in deductive verification

texts:
I have been studying deductive verification of software lately, with weakest precondition, strongest postcondition, annotation calculus, and etc.
I came across the following rules for the while sentence:

But, my problem is when should I use which rule? I mean the second and third one that includes $t$, which is the variant here, is usually related to the loop condition, but when again when should I use the second while and when the third one? I couldn't find any clarification anywhere about when to choose which one.  (Note that $t$ is not a variable of the program, but a variant used to prove termination.)


texts: Running an application that needs 6 threads on dual core processor

texts:
If a dual core processor have 4 threads, then what will happen if i run an application which uses more than 4 threads?
And just to make sure i'm understanding what are threads in a cpu, when an application uses more than one "task" on its main process a single core will switch back and forth between the threads to give the illusion that it is running them in parallel, is that right?


texts: How to prove that an algorithm has no deadlock

texts:
I need to mathematically prove that this algorithm is deadlock-free:

semaphore semA = 1;
semaphore semB = 3;

process P {
    while (true) {
        P(semA);
        <print “TA”>;
        V(semB);
    }
}

process Q {
    while (true) {
        P(semB);
        P(semB);
        P(semB);
        P(semB);
        <print “RA”>;
        V(semA);
        V(semA);
        V(semA);
        V(semA);
    }
}

This program prints a sequence of "TA" and "RA" according to its synchronization rules. I know how to prove its correctness starting from the invariant $-3 \le n\mathrm{TA} - 4n\mathrm{RA} \le 1$ but I don't how to start to prove that is deadlock-free. Do I need to count the number of P(semA)/P(semB)?


texts:
In Sipser, It is given Pg. 284

Let t(n) be a function, where t(n) ≥ n. Then every t(n) time
non-deterministic single-tape Turing machine has an equivalent 2 O(t(n))
time deterministic single tape Turing machine

In the given proof, at end they conclude

O(t(n)bt(n)) = 2O(t(n)).
where b is the maximum number of legal choices given by N’stransition function

I am unable to understand how did they conclude so>


texts:
I was going through the B+ tree deletion operation from the book Database System Concepts, 6th Edition by Henry F. Korth. One particular thing caught my attention.

A B+ tree is given. We have to delete the record "Gold" from this tree.

So we first locate the record by going down the tree and once we find the node, we delete the record. But this deletion leaves the node underfull, because a leaf node has to be at least half full or it has to have at least $\lceil{\frac{n - 1}{2}}\rceil$ values, where $n$ is the maximum number of pointers in each node.

So we merge the rightmost two nodes. But this leaves their parents left pointer pointing to nothing. We again have a violation. Because the internal nodes need to have at least two pointers. To get around this, we merge the parent with its sibling. Resulting tree is given below:

Now the problem I'm having is that, why the record "Gold" has been moved down? We could have just as easily moved the record "Katz" up without violating anything. And it makes more sense to me, because we've just deleted "Gold". So can anyone explain to me why this has been done like this in the book? And would I be right in saying that things would be the same if "Katz" had been moved up?