Recursive algorithm to find maximum value in 2D array Imagine a 2D array of size n x m, where every column is a stack of positive values. I am trying to figure out a recursive pseudo code algorithm, where I have a number k, that is the maximum number of elements to pick from the array, which would find the indices in every column, that would maximise the sum of all the values of that index and all values above it.
[5 7 8]
[2 0 1]
[1 4 3]

For example here, if I took the number k to be 4 then I could only pick 4 values, s.t. the sum of them is maximised. For example, index 1 in the first column (value 2), index 0 in the second (value 7) and third column (value 8), which would result in
5 + 2 + 7 + 8

But I cannot grasp how could I implement the recursive algorithm to solve an issue like this. Would be grateful for any directions on this matter.
Thank you!

You can solve this using dynamic programming. For each $i$ and $\ell \leq k$, find the best solution for the first $i$ columns, when you are allowed to pick at most $\ell$ values.


What is the basic idea behind the usage of TLBs? I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache.
The problem is that i can't understand why frequent memory locations are acccessed in a period of time? And what was the starting point of this idea:

  "Since the same memory locations are accessed frequently, We can create a place to hold the frequent translations so that make everything happen faster."

Can someone please share the knowledge behind this concept? Thanks.

A TLB is useful for the same reason any other cache is useful: because it's very common to access the same data multiple times in quick succession. Many algorithms use the same value more than once. For example, searching requires accessing the search pattern a lot of times. Sorting a list requires comparing the same element multiple times for any (comparison-based) algorithm.

The nature of the TLB amplifies this effect because it doesn't only kick in when accessing the same data, but more generally when accessing data in the same page. This happens even when each individual bit is only accessed once. For example, consider a simple array traversal, that accesses the array elements in order. Assume that elements are smaller than one page, say $k$ elements fit in a page. Then a single MMU lookup is needed for the first element in a page, and the next $k-1$ only require a TLB lookup.


Difference between Bandwidth and Propagation Speed in computer networks? I want to know the difference between Bandwidth and propagation speed. How are they associated with each other i.e. the impact on bandwidth if propagation speed varies or the impact on speed if bandwidth varies. I have gone through this difference between propagation speed and bandwidth in digital communication still I am unable to understand it very clearly. Could it be possible to explain with some other example like may be with water pipes etc.

These two terms are actually completely unrelated. Bandwidth is a way of expressing how much "stuff" you can send on a network link at a time. Think of it like a highway. If you have only one lane on the highway, then you have a bandwidth of 1 car per some unit of time (let's say seconds). So every second, only 1 car can pass through that particular segment of roadway. But if you widen the road to have 4 lanes, then you can get 4 cars per second. It's literally the width of the frequency band you can send data over.

Now propagation speed is how quickly something can propagate, or move a certain distance. Consider the cars again. If they are driving 60 mph, then then it will take one hour to travel 60 miles. Regardless of how many lanes are on the highway, each car will still take one hour to travel that whole distance. Cars in the front and the back of each lane will take one hour. By the way, the reverse is true as well: increasing the speed of each car has no affect on how many you can fit side by side on any stretch of road.


Maximizing the minimum of $k$ submodular functions Let $f(X)$ be a monotone submodular function from $2^{\{1, \ldots, n\}}$ to $\mathbb{N}$ and consider the problem of maximizing it subject to a cardinality constraint $|X| \leq m$. By using the greedy algorithm, it is possible to obtain a $1-1/e$ approximation (see, for example, these lecture notes).

But now suppose $f_1(X), \ldots, f_k(X)$ are monotone submodular functions and we want to maximize $\min(f_1(X), \ldots, f_k(X))$ subject to the same cardinality constraint. Is it still possible to obtain a constant factor approximation?

Krause, McMahan, Guestrin and Gupta, who call this problem Robust Submodular Observation Selection show that is is NP-hard to approximate this problem to within any constant.


Proof for "It is my contention that these operations include all those which are used in the computation of a number" In his famous paper, Turing briefly describes his machine and then states (p. 232) (emphasis mine):

  It is my contention that these operations include all those which are
  used in the computation of a number. The defence of this contention
  will be easier when the theory of the machines is familiar to the
  reader.

Does this mean that all numbers that could ever be computed by a machine or a human being can be computed by a Turing Machine?

If yes, what proof has Turing, beside "It is my contention"?
Does Turing defend this contention later on, in the same paper or elsewhere?

A contention is something that one asserts to be true. Turing's contention here is essentially the Church–Turing thesis: that Turing machines can compute everything that can be reasonably computed. This isn't something that can be proven without a definition of "reasonably computed". But, even if one were to define that term, it would be arguable that the definition wasn't a good one and that, again, isn't something that can be proven.

Turing's paper includes a lot of material about computable sequences of numbers and also a sketch proof that Turing machines and the lambda calculus are equally powerful. That constitutes quite a lot of evidence for the original contention, though I didn't notice Turing explicitly mentioning this when I skimmed the paper just now.

In particular, one might choose to define "reasonably computable" as meaning "computable by any possible physical system." Well, Turing machines can simulate every physical process we're aware of, including quantum mechanics. But, of course, we can't prove that there are no physical processes we don't know about yet that can't be simulated by Turing machines.


What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path? I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the random element?

There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund [1]. These algorithms are often algebraic and the "random element" stems from the application of the Schwartz–Zippel lemma. Usually, the algorithms work so that the graph property we are interested in is somehow represented as a (multivariate) polynomial with the property that that a solution exists precisely when the polynomial is not identically zero.

[1] Björklund, Andreas. "Determinant sums for undirected hamiltonicity." SIAM Journal on Computing 43.1 (2014): 280-299.


Proving that $A=\{w_{2i}|w_{2i}\not\in L(M_i)\}$ is not Turing-recognizable In this problem, $w_{2i}$ is the $2i$th string in the lexicographic order of binary strings and $M_i$ is the TM whose binary code is $w_i$.
We are given the diagonalization language $A_D=\{w_i \mid w_i \notin L(M_i)\}$. We know $A_D$ is not Turing Recognizable.

Basically, $w_i$ is the $i$th string in the following lexicographic ordering:
$\epsilon, 0, 1, 00, 01, 10, 11, ...$

The proof for $A_D$ is the following: Suppose by contradiction, there is a TM $M$ such that $A_D = L(M)$. Then $M=M_i$ with code $w_i$ for some $i$. $w_i \in A_D$ iff $w_i \notin L(M_i)$ by definition of $A_D$. $w_i \in A_D$ iff $w_i \in L(M_i)$ by $A_D = L(M_i)$. A contradiction.

The problem is I don't understand the proof above. Therefore, I have no idea how to approach the topic question. It would be very helpful if someone can give a brief explanation of how $A_D$ proof works and what approach I can take to prove $A$ is not Turing recognizable. For instance, is it possible to reduce $A_D$ to $A$? Or is it better to follow the same proof format as $A_D$?

Lets reformat your language $A_D$ to say $A_D=\{ \langle M \rangle| \; \text{M is a Turing machine ( TM ) and does not accept }\langle M \rangle\}$. Here $\langle M \rangle$ means encoding of Turing machine $M$, and I assume the inputs are always valid encodings TM's ( as you can always check if a string is a valid encoding or not ). Now say there was a decider for $A_D$, let it be $D$. Now if you give input $\langle D \rangle $ to $D$ it has to halt ( we assumed it is a decider ) and either reject or accept. If it accepts it, it means $\langle D \rangle  \in A_D$ and thus $D$ does not accept $\langle D \rangle $, which is a contradiction. If $D$ reject $\langle D \rangle $ it means $D$ accepts $\langle D \rangle $ acccording to definition of $A_D$ which again is a contradiction. Either ways it is a contradiction, thus our assumption that $D$ exists is not correct and $A_D$ is undecidable ( this proof is related to Cantor's diagonal method ) .

This logic cannot be applied to prove $A_D$ is not  Turing recognizable. I leave the reason for you to figure out ( hint: no assumption about halting on all inputs is made ).

I will prove non recognizability  of a general language ( which implies undecidability  ) instead of $A_D$ and the one you specify in your question.
$L=\{  w | \; f(w) \;\text{ is a valid encoding of some Turing machine where } f \; \text{is some computable function and the Turing machine given by } \; f(w) \; \text{does not accept} \; w\}$
( $f$ is such that  for every TM encoding $\langle M \rangle \exists w $ s.t. $ f(w)=\langle M \rangle$ )
Now suppose $L$ was Turing recognizable, let the TM  be $R$. We construct another Turing machine $H$ which given an input $w$ first finds $f(w)$ ( again assuming it is a valid encoding of a TM, if not $H$ can directly reject ). Then $H$ gives $w$ to $R$ and simulates $w$ on $f(w)$ in parallel. If $f(w)$ accepts $w$ $H$ rejects, if $R$ accepts $w$, H accepts. This way you are able to decide language $L$ which is undecidable. You can prove $L$ is undecidable yourself ( see when $f$ is the identity function, $L$ reduces to $A_D$ which is undecidable ).
I leave it for you to figure out how non recognizability of $L$ can be used for proving that of your languages.


About the definition of a balanced tree (Note: I couldn't put "balanced tree" in the tags ; this topic isn't about balanced search trees, just balanced trees.)

Let $A$ a binary tree.

We have the relation: $log(|A|+1) \leq h(A) \leq |A|-1$ where $|A|$ denotes the size of A (the number of nodes) and $h(A)$ its height.

Then I was told that A is balanced if $h(A) = O(log|A|)$. I don't really understand what that means. I know the symbol $O$ when we use it in maths with "$n$" stuff. For exemple $u_n = O(v_n)$ when $n \to +\infty$ or $f = O(g)$ at a certain point $x$. But there, how can we told that the tree $A$ "evolves"?

Applying the definition, it would mean that $\frac{|A|}{log|A|} \leq M$ but for a given tree, this is always true. So do we fix set the tree's size and have the relation for any size or do we fix the size and have the relation for any height, or something else?

Thanks.

You're right – a single tree cannot be balanced, or rather, is trivially balanced. A collection of trees can, however, be balanced meaningfully: there exists a constant $M$ such that all trees in it have height at most $M\log n$, where $n$ is the number of elements in the tree.

For example, take any algorithm that uses a binary tree. We know that operations on binary tree take time $O(h)$, where $h$ is the height of the tree. Suppose now that the algorithm maintains the property that the tree is balanced; that is, the set of all trees that occur in all executions of the algorithm forms a collection of balanced trees. Then we can bound the running time of operations on the tree at a certain point in time by $O(\log n)$, where $n$ is the number of elements in the tree at that point.

In practice, we "misuse notation" by calling a single tree balanced. What we mean that the set of all "instances" of the tree are balanced. Usually what set is meant is clear from context.


Why don't computers use the same architecture? We just started on the Computer Architecture topic in our CS lectures and I have a few questions that are currently bothering me. So we have different computers, and there are always differences in the hardware and architecture.

Now, why don't all computers simply use the same architecture? Won't that make it easier to program? What makes this a bad idea?

Why aren't all cars identical? Wouldn't that make easier to build and repair them?

There are big and small cars, cheap and expensive cars, fast gas guzzlers and slow energy savers… And similarly there are many different types of computers.

Here are a few criteria that influence the architecture of a computer. Optimizing for some of the criteria will have a cost against some other criteria.

Speed to execute sequences of integer operations
Speed to execute sequences of floating-point operations
Speed to execute sequential computations that require a lot of memory
Speed to make parallelizable integer computations
Speed to make parallelizable floating-point computations
Speed to make parallelizable memory-intensive computations
Power consumption when idle
Peak power consumption
Ability to scale power consumption according to the amount of computation at a given time
Special-purpose computations (graphics processing, cryptography, digital signal processing, …)
Volume
Design cost
Per-unit manufacturing cost for large amounts
Per-unit manufacturing cost for small amounts
Possibility to connect many peripherals
Ability to execute tasks in real time, i.e. fine control over the execution time of each operation (e.g. to control a physical object)
Isolation between tasks (for robustness and security)

This is of course not an exhaustive list. In practice, you'll find architectures that find a few sweet spots, optimizing for some criteria at the expense of others.

Here are a few examples of different compromises.

Intel x86 processors tend to be very good at raw speed for sequential execution of pure computation and memory accesses. ARM tend to be less fast, but consume less power, which is a large part of why x86 is so common on computers that are plugged into the mains while ARM is prevalent on computers that almost always run on battery such as mobile phones.
GPU are very good at executing many tasks in parallel, which is well-suited to drawing images that consist of millions of pixels. But they're bad at accessing lots of memory in random ways, so they don't make good general-purpose processors.
An MMU translates memory addresses used by programs into memory addresses used by the hardware. This allows the operating system to execute programs each in their own address space, so that they don't interfere with each other. This means that each memory access can take a variable amount of time, though, which is why most processors designed for real-time systems don't have an MMU.
FPGA are extremely flexible processors — you can reconfigure them to optimize them for whatever computation you want to do today. But they aren't cheap.

Add to that historical factors. Designing a new processor architecture takes years of effort by teams of hundreds or thousands of highly-trained engineers, and changing architectures involves rewriting a lot of software, so it doesn't happen often. So just like you can have different car models from different manufacturers that have the same strengths and weaknesses, you can have different processor architectures from different manufacturers that vie for the same applications.


Imperfection in randomness in VLC shuffle playlist - why? Whenever I play a playlist of music using VLC (possibly other software too), I notice that some songs never get played while others get played repeatedly (even for a playlist of just 8 songs).

I know from my days as a computer science undergrad student that practical randomness is often good enough so we don't bother with true randomness for many applications. But I'd like to understand this better.

why is real randomness not worth the effort?
does pseudo-randomness not follow a uniform distribution?
are software developers perfectly aware of behavior like I see in VLC and just see a tiny market segment as caring about it?

EDIT: actually, my VLC issue might be because of a broken link! But I'm sure I've seen this behavior with other music players like Apple Music. So apologies to the good folks who develop VLC.

This is just speculation, but perhaps what VLC is attempting is to simulate... perfect randomness. That is, each song is picked uniformly at random, independently of previous songs. According to the coupon collector problem, if you have $n$ songs in your list and want to hear all of them, you will have to wait for roughly $n\ln n$ songs to be played. By that time, the average song will have been heard $\ln n$ times.

The problem seems to be not in VLC, but rather in the random experiment that VLC is trying to simulate. VLC is not trying to shuffle your playlist and play it through. Rather, it seems to just pick a new random song each time, regardless of the past.


Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al. where I came across the following excerpt.

Example 4.11. Consider the abstract language $L_1 = \text{ { $wcw$ | $w$ is in $(a|b)^*$}}$. $L_1$ consists of all words composed of a repeated string of $a$'s and $b$'s separated by a $c$, such as $aabcaab$. It can be proven this language is not context free. This language abstracts the problem of checking that identifiers are declared before their use in a program. That is, the first $w$ in $wcw$ represents the declaration of an identifier $w$. The second $w$ represents its use. While it is beyond the scope of this book to prove it, the non-context-freedom of $L_1$, directly implies the non-context-freedom of programming languages like $\text{Algol}$ and $\text{Pascal}$, which require declaration of identifiers before their use, and which allow identifiers of arbitrary length.
For this reason, a grammar for the syntax of $\text{Algol}$ or $\text{Pascal}$ does not specify the characters in an identifier. Instead, all identifiers are represented by a token such as $\text{id}$ in the grammar. In a compiler for such a language, the semantic analysis phase checks that identifiers have been declared before their use. □

I can understand that since $\text{Algol}$ and $\text{Pascal}$, require declaration of identifiers before their use we cannot check this property using context free grammar. But what is the connection of this with the point of "allowing identifiers of arbitrary length"?
Moreover the authors add, that instead of using the characters in an identifier, identifiers are represented by the token class $\text{id}$. That the identifiers are represented by the token class $\text{id}$, was known to me as a fact, but I did not quite know what is the significance of this as far as the explanation in the example of the text is concerned.
Please explain me.

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language
$$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$
is context-free (indeed, regular).
The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; this will be checked on-the-fly by the parser. This idea is implemented by representing identifiers as a single token in the grammar of Pascal or Algol.


How static Bayesian networks are stored? Like Hugin etc I wanted to know the standard format to store the Bayesian network structure? I came across Hugin format and others. But couldn't find out the documentation as how its been written, if I wanted to write a piece of package that writes the BN in a file which can be read by other popular Bayesian inferencing tools for Bayesian networks.

For anyone who shares this same query. I have found a link that answers it. Further, found a implementation as well.


Does an algorithm have to terminate? I was reading about the finiteness property of an algorithm where it is mentioned that

  the algorithm must always terminate after a finite number of steps.

Does this mean that any pseudo-code cannot contain infinite loops or it should be equivalent to Halting Turing Machine.  I don't know whether the statement about finiteness property of an algorithm is correct or not. I have not found any reliable source for it and I have not read it in CLRS.

My question is whether the statement and whether my interpretation about it is correct:

  An algorithm must always terminate after a finite number of steps

References:

Intro Problem Solving in Computer Science, CS@VT (Page 3)
Wikipedia article on Algorithm_characterizations
Data Structures and algorithms, CmpE, Boun

Yes, an algorithm should always stop after a finite number of steps, otherwise we would call it a procedure or process or computation specification.  A procedure that doesn't halt for certain inputs can be considered partial algorithms.  Algorithms are more useful, since they terminate for any input.

An algorithm can be viewed as a function $f: \mathbb{N} \to \mathbb{N}$.  if it is defined for all input values, we say that $f$ is "total" ; for an algorithm, it means that it halts for any input.  On the other hand, if a function $f$ is "undefined" for an input, say $4$, we say that $f$ is a partial function, and in computation theory, we write $f(4)\uparrow$ meaning it "diverges", or simply "doesn't halt".

An example for a partial function can be the inverse of the integer square function, i.e. $sq(n) = n^2$.  The inverse, $sq^{-1}$ is defined only on perfect squares, that is, $$sq^{-1}(n) = \cases{\sqrt{x} \text{ if $x$ is a perfect square} \\ \text{undefined otherwise.}}$$


Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic So a tournament is just a complete directed graph, I believe.

I'm having trouble proving this problem. I know it is induction however. I was thinking
the base case is $2^1$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $2^{n + 1}$. But I'm not sure how to approach this. Any ideas would be extremely appreciated.

A tournament is a loop-free directed graph $G=(V,E)$ in which, for each pair of distinct vertices $u,v \in V$, exactly one of $(u,v)$ and $(v,u)$ is in $E$.

The proof of your claim is by induction.

For $n=0$ the claim is true since a tournament $G$ with $2^0=1$ vertices is trivially acyclic, and its only sub-tournament with $0+1=1$ vertices is $G$ itself.

Assume now that the claim holds up to some $n \ge 0$ and consider a tournament $G=(V,E)$ with $|V|=2^{n+1}$. Pick an arbitrary vertex $v \in V$, and partition the vertices of $V \setminus \{ v \}$ into two sets $L = \{ u \in V \setminus \{ v \} \mid (u,v) \in E \}$ and  $ R =\{ u \in V \setminus \{ v \} \mid (v,u) \in E \}$.
One of $L$ and $R$ must contain at least $\left\lceil \frac{|V \setminus \{v\}|}{2} \right\rceil = \left\lceil \frac{2^{n+1} - 1}{2} \right\rceil=2^n$ vertices. Arbitrarily select $2^n$ vertices from this set, and call the set of the selected vertices $S$.
By inductive hypothesis $S$ contains an acyclic sub-tournament $S'$ of size $n+1$, and since either $S' \subseteq S \subseteq L$ or $S' \subseteq S \subseteq R$, we have that $S' \cup \{v \}$ is also acyclic. This proves the claim since $|S' \cup \{v \}| = |S'| + 1 = n+2$.


Set notation for ACL matrix This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation and I wonder if someone could break it down for me?
$$A’[s_i,o_j]=A[s_i,o_j] \; ∀(s_i,o_j)≄(s,o)$$
I understand that $A’[s_i,o_j]$ is the new resulting matrix after some operation and I think $s_i$ and $o_j$ are the matrix pairs that are not being amended although I do not know exactly that this is the case or how adding the $i$ and $j$ denotes this.
This might be way off the mark but is it saying that the new matrix is equal to the old matrix where none of the pairs are equal to the pair being deleted?
I am also looking at a list of set symbols and I cannot find this $≄$ listed.

The notation means:

For any $(s_i,o_j) \neq (s,o)$, $A'[s_i,o_j] = A[s_i,o_j]$.

The correct symbol seems to be $\neq$, "not equal", rather than what you wrote.
The symbol $\forall$ means "for all".
The notation $s_i$ just means "element number $i$ in the set of rows", and $o_j$ is similarly "element number $j$ in the set of columns". You could just as well have replaced $s_i,o_j$ with any two other symbols (other than $s,o$).


How does storing encrypted password provide secure authentication? It's universally accepted that storing an unencrypted password for automated authentication is a very bad idea, for the saved password can be used by malware, etc.

There is a number of systems that store encrypted passwords for the purpose of automated authentication elsewhere. For example, one can configure git to automate authentication during git push. My question is: how do such system manage to authenticate securely?

Specifically, here are two possibilities:

1) The local system stores the encrypted password, and when needed, sends it to the remote system. The remote system accept the encrypted password for authentication.

However, in this case the encrypted password leads to exactly the same vulnerability as unencrypted password: malware can use the unencrypted password to authenticate itself. For example, if your password was "brown fox" and it was stored as a hash 14921776, and the remote system would accept 14921776 as a valid authentication certificate, then malware can just look up 14921776 in the encrypted password file in the local system and use it as is.

2) Suppose now that the remote system does not accept the encrypted password for authentication. In the above example "brown fox" needs to be communicated between local and remote system; the hash 14921776 won't do.

How does the local system would provide automated authentication in that case? All the local system knows that the hash of the password is 14921776, but it cannot unhash it into "brown fox", and therefore cannot send the valid password to the remote.

Actually, storing an unencrypted password can be OK in certain circumstances, depending on what the password is used for and the threat model you are trying to defend against.

In any case, if you are authenticating to a remote system, you probably should be using public-key cryptography instead of a password if you possibly can.

Some relevant readings:

https://security.stackexchange.com/q/12332/971
https://stackoverflow.com/q/2283937/781723
https://security.stackexchange.com/q/184021/971
https://security.stackexchange.com/q/20294/971
https://security.stackexchange.com/q/143338/971
https://security.stackexchange.com/q/129776/971
https://security.stackexchange.com/q/22760/971


complexity of a variant of the subset sum problem We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$.

What is the complexity of this problem.

It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".


Pumping Lemma: 1^n^2 is not regular I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with

$w = 1^{p^2}$

I then divided $w$ into $xyz$, where:

$x = 1^{l}$

$y = 1^{m}$

$z = 1^{{p^2}-l-m}$, where $l+m \le p$ and $m \ge 0$.

Now, when I choose $i=2$ in order to get $xy^2z$, I end up with:

$1^{{p^2}+m}$, since $0 > m \le p $, the sum $m+p^2$ could certainly not be a square because the difference between $p^2$ and the next square is always greater than $p$ for all natural numbers.

Q.E.D

However, even if the basic logic of the proof is right, it does not seem as if my conclusion is as strong as it should be. Is there a more formal, proof-like manner to reach my conclusion with the same $s$ and $xyz$?

Your proof is correct, but you could elaborate your arguments if you wish.

We have $m\gt 0$ (typo in your question I think, you have used $\ge$) and $l+m\le p$. As $l\ge0$, $0\le p-m\implies m\le p$

$$m\gt0\implies p^2+m\gt p$$
$$\begin{align}m\le p&\implies p^2+m\le p^2+p\lt p^2+2p+1=(p+1)^2\\
&\implies p^2+m\lt (p+1)^2\end{align}$$

$p\lt 2p+1$ is true because $p\ge1$.

Thus, $p^2+m$ lies strictly between two consecutive squares, and hence cannot be a perfect square.


Undecidability of the language of all Turing Machines with repeat strings as their language Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable.
I would prefer if reduction was used and not Rice's theorem.

Imagine a fixed machine $M$ and a fixed string $w$ and then let $M'$ be the machine that on input $x$ simulates $M$ on $w$, and if that simulation halts then answers Yes if $x=ab$ and No otherwise.
How could you decide whether $M'$ belongs to your language? You would need to know whether $M$ halts on $w$! As in that case $L(M')=\{ab\}$ and otherwise $L(M')= \varnothing$.
Details up to you :)


Reinforcement learining basics - is it possible to deal with environment with random events As part of data science course I would like to solve particular problem with reinforcement learning algorithm.
I believe I understand general concept, however the problems I had read about up till now had no random factor included. I would like to ask if it's valid to assume that reinforcement learning algorithm will be able to find "good" (somewhat close to optimal) solution when, at each step, one or more random events can occur, provided that we know the probability of those events?
For practical example that I can think of: let's say we have to find exit from labyrinth as quick as possible, on each turn we can decide to rest or move. If we move, we become more tired, which increases probability that we will fall and twist our ankle (if this happens our speed is reduced for several turns). We know what's the probability of falling on each turn, but we do not know if this will really happen or not. During rest we reduce probability of falling.
In my project I would like to include several (around 5) of such random events.
Is it correct to assume that reinforcement learning algorithm should be able to find a valid solution, despite such random factors? We can define "valid" as, for example, in 90% of cases taking less than X turns. If yes, I would highly appreciate if you could point me in right direction, or to any materials describing practical solutions to such problems.
Thank you in advance for your input and sorry in case this question is really basic (hopefully not)!

Yes, in general reinforcement learning algorithms can handle random events in the environment. Think about the q-learning update rule
$$ Q(s_t,a_t)= Q_{s_t, a_t} + \alpha \left(r_{t+1} + \gamma max_aQ(s_{t+1},a)\right) $$
But remember $$Q(s_{t+1},a) = \mathbb{E}_\pi\left( \sum_{i=t+2}^T\gamma^{i-1}r_{i} \right)$$
that is the expected value of the discounted sum of future rewards. This handles randomness in the environment quite well and eventually the value will adjust to factor in these random events. In a tabular environment this will always converge to the optimal value function and corresponding policy.
If you know the environment dynamics (which it seems like you do here)
$$ p\left(s', r\mid s,a\right)$$
you can use a dynamic programming method like policy iteration or value iteration to efficiently compute an optimal policy and value function. I recommend looking at the first 4 chapters of Reinforcement Learning: An Introduction by Sutton and Barto (at least chapters 3 and 4). The text is available freely online on their website at their website.


Regular Language - Context Free Language I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question

  Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet
  $\sum^*$, which of the following about the langauge
  $R=\overline{A}-B$  is  $TRUE?$

  a. $R$ is necessarily $CFL$ but $not$ necessarily $regular$

  b. $R$ is necessarily $regular$ but $infinite$

  c. $R$ is necessarily $non$ $regular$

  d. $None$

  e. $\phi$

Now I have approached this problem in 2 ways and I am getting 2 different results.

The first way in which I have approached is that, since $A'-B=A'\cap B'$, so it is $Reg$ $L$ $\cap$ $CSL=CSL$ , so answer is $NONE$

On the other hand I have think of it like this, since $A$ is $Regular$ it's complement is also $regular$, Now we know that

So $regular$ $language$ being a subset of $CFL$ must give us $\phi$ when we are doing $A'-B$, so this time I am getting $\phi$ as answer

My question is which of my approach is correct? Is the first one correct? If so, then why the second one is wrong?

Or is the second one correct? If so then why the first one is wrong?

I believe that the second method shown by me is wrong as say we have a regular language  $A=\phi$, so $\overline{A}=\sum^*$ and say $B=a^nb^n$

then $\overline{A}-B=a^xb^y$, where $x\neq y$, so it is a $CFL$ but not $\phi$.

So where did I went wrong in my second proof using $Chomsky$ $hierarchy?$

Downvoters(if any) please mention the reason of downvote in comment. Thank you.

Your second method to arrive at $\phi$ is bogus - consider the case where $B$ is the empty language. Where you are confused here is you are looking at the difference between the sets of all regular languages and all context free languages, instead of the difference between the two concrete languages.

The correct answer is d. None  (you can't say anything)

Because

$R=\overline{A}-B = \overline{A \bigcup B} $

Since $A \bigcup B$ is clearly a $CFL$, this answer applies which states that the complement of a $CFL$ is not necessarily $CFL$ itself ($CFL$ are not closed under complement).


Cognitive Computing vs Artificial Intelligence? Can anyone please tell me the difference between them?
A brief definition of Cognitive Computing would appreciated.

Also how does cognitive computing relate to neural networks?

A brief definition would be:

  Cognitive computing is the simulation of human thought processes in a computerized model.

more detailed explanation:

  Cognitive computing involves self-learning systems that use data mining, pattern recognition and natural language processing to mimic the way the human brain works. The goal of cognitive computing is to create automated IT systems that are capable of solving problems without requiring human assistance.

Cognitive computing is used in A.I. applications. Therefore I think it can be concluded that Cognitive Computing is a subset of Artificial Intelligence.

Cognitive Computing systems may include the following ostensible characteristics:

Natural Language Processing
Machine Learning
Algorithms that learn and adapt
Vision-based sensing and image recognition
Spatial and contextual awareness
Reasoning and decision automation
Sophisticated pattern recognition
Neural Networks
Semantic Understanding
Noise Filtering
Common Sense
Robotic Control
Emotional Intelligence

So basically, you can say that a cognitive computing system might be trained by neural networks.

Sources:

http://www.cognitivecomputingforum.com/
http://whatis.techtarget.com/definition/cognitive-computing


Is master theorem applicable for $T(n) = 8T(\frac{n-\sqrt n}4) + n^2$? Is master theorem applicable for this example?

$$T(n)= 8T \biggl(\frac{n-\sqrt n}4\biggr)+ n^2$$

The master theorem isn't applicable, but the Akra–Bazzi theorem is, and it shows that your recurrence has the same solution (asymptotically) as the simpler one without the square root, that can be solved using the master theorem.


Proving that $2^n$ does not divide $n!$ How can prove that $2^n \nmid n!$
using binary representation for $n!$ and $2^n$.

Idea: Count explicitly how many factors $2$ the numbers in $[1..n]$ contribute to $n!$.

Observe that every other number adds one (the even numbers), every fourth adds another (those divisible by four), every eighth another, and so on.
Hence, the number $\#_2(n!)$ of factors $2$ in $n!$ fulfills

$\qquad\displaystyle\begin{align*}
  \#_2(n!) &\leq \sum_{i=1}^{\log_2(n)} \frac{n}{2^i} \\
           &= n \cdot \sum_{i=1}^{\log_2(n)} \frac{1}{2^i} \\
           &= n \cdot \frac{n-1}{n} \\
           &= n-1 \;.
\end{align*}$

Therefore, $2^n$ can not be a divisor of $n!$.


DFS & BFS Spanning Trees I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one.

DFS:

My understanding that to the construct this DFS where each next is the cheapest one, the resultant spanning tree would be:

  {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)}

BFS:

My understanding that to the construct this BFS where each next is the cheapest one, the resultant spanning tree would be:

  Queue: a  c   d   b   e   f   h   g   k   m   i   j   k

Is my understanding of spanning trees correct when the next edge to be traversed should be the cheapest one? Is this a MCST?

You can construct a DFS spanning tree or a BFS spanning tree in many ways. You could require the next edge to be traversed should be the cheapest one available, if that helps in any way or if you just like to do that. As long as you are using DFS or BFS, you will end up with a spanning tree.

However, if you do want to always traverse using next cheapest edge among all possible choices, "Queue: a c d b e f h g k m i j k" for BFS should be "Queue: a c d b e f h g k m i j l", which is I assume a typo.

"Is this a MCST?" No, none of the two is a minimum cost spanning tree, which is more commonly called minimum spanning tree (MST). The DFS spanning tree, {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)} could have less cost if (g,f) is replaced by (c,f). The BFS spanning tree, {(a,c), (a,d), (a,b), (a,e), (c,f), (c,h), (b,g), (b,k), (e,m), (h,j), (k,l)} could have less cost if (b,g) is replaced by (h,g). As you can see, there is no guarantee that a MST can be obtained if you use a DFS or BFS.

In fact, for this particular graph, no matter how you conduct BFS or DFS, you will not end up with a MST.


Turing Machine for strings without bbb I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \{a, b\}$.

When I implement this graph in JFLAP, I'm receiving an error that there are transitions out of final states. Is it OK to construct a transition graph like this, or is it considered bad practice? If so, can you help me understand the correct way to construct the transition graph?

The state $q_3$ is not necessary, because you couldn't have string with the pattern $bbb$ inside of them. So, just delete it. The next automaton accepts your language requirement.

Hope it helps


Which type compilers report if they cannot infer a precise type? In the presence of subtyping, a type checker can usually infer only some inequality constraints on the type rather than the exact type. Of course, internally it will store the full constraints. But what is the common practice in case it needs to display the inferred type to the programmer?

I thought it might be reasonable to just display the lowest type that satisfies all the constraints (I guess it exists and unique if the types form a lattice). That would mean the programmer would know all the contexts where the name can be used. But then, if there's no constraint from below, the type checker would be displaying Bottom, and I don't think it's commonly done.

What am I missing?

It is important to keep in mind that this is a question about human-computer interaction and not about compilers. As far as the machine is concerned, the constraints are the constraints, and the obvious thing to do is just to show all the constraints to the user. However, when the user is a human, they may find the constraints too complex to process, and so the machine needs to dumb down the information for the cognitively handicapped user. This is in fact what happens, see for instance Pretnar's paper on inference for effects where he discusses what to show the user (that's just the first paper that came to my mind, and is by no means the only one or the first one).

As you notice, showing just the lower bounds may be useless. Symetrically, showing just the upper bound may be useless as well. However, in many situations one has either useful lower bounds or useful upper bounds, in which case you just show the useful part (and you need to indicate whether you're showing the lower or the upper bound). Other than that, people try various strategies. A common one is to simplify the constraints in the hope that we won't lose much information, and then show those to the user. Simplification can also be useful to control the size of constraints, which can easily grow so much that the whole system becomes useless.


Is the number of inequivalent elementary cellular automata rules really 88? Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia article).

Now, the problem is that I am failing to reproduce the 88 number. No matter how I try - I always get 72.

And it gets worse. Sequence A005418 seems to be defined exactly as Wolfram's inequivalence (see the comment: "Number of bit strings of length (n-1), not counting strings which are the end-for-end reversal or the 0-for-1 reversal of each other as different."). And in that sequence at position 8 they also have 72, not 88.

Off course, there is a chance that my program is wrong and/or I do not fully understand the definition of rule equivalence. Therefore I would like to ask someone to reproduce the computations, and either confirm Wolfram's original number 88, or give me the correct number of inequivalent rules (be it 72, or something else).

This problem is important for a research paper I am working on. And it's not very difficult to implement.

OK! Peter de Rivaz has confirmed the number $88$ by careful analysis of the two equivalence rules, and a clever script.

Here I will try to repeat the analysis (for my own understanding) and then apply some mathematical magic.

A binary cellular automaton is denoted by a bit string $ABCDEFGH$ where the consecutive letters denote each a bit (next state) for the three bits that encode the configuration at position with its two neighbours, $xyz = 111, 110, 101, \dots, 001, 000$.

The mirror operation is the automaton in left-right reverse, meaning that the bit for $xyz$ is now at $zyx$. Thus $A$ at $111$ stays in place, but $B$ at $110$ is swapped with position $E$ at $011$. The new rule is then $AECGBFDH$. There are $64$ rules that stay unchanged under this operation. Says Wikipedia.

The complement operation is the automaton with bits swapped, meaning that the bit for $xyz$ is now the negation of bit $\bar x\bar y\bar z$, which looks rather DeMorgan to me. In words, the bits are reversed and inverted. The new rule is then $\bar H\bar G\bar F\bar E\bar D\bar C\bar B\bar A$. There are $16$ rules that stay unchanged under this operation. Says Wikipedia.

We can also combine the two rules. Mirror complement gives $\bar H\bar D\bar F\bar B\bar G\bar C\bar E\bar A$. Again there are $16$ rules unchanged under this rule. The math is easy, unchanged means $A=\bar H$,  $B=\bar D$ etc, finally leaving $4$ free variables.

Applying no operation identity keeps all $256$ bit strings unchanged. Also any combination of mirror and complement will again be one of the four above operations (but you have to convince yourself on that).

The magic is Burnside's Lemma: the number of orbits under a group $G$ of permutations of a set $S$ equals $\frac1{|G|}\sum_{\psi\in G}|\text{fix}(\psi)|$.

The number of orbits here is the number of inequivalent cellular automata. Let's check the math: $\frac14(256+64+16+16) = 352/4 = 88$. This (again) confirms the number on Wikipedia.


What is the semantics of a Turing machine? Can we formalize the operational/denotational semantics of a Turing Machine? Is there any formalization in literature?

The usual definitions of Turing machines are given in terms of formal semantics. For instance, the Wikipedia definition describes Turing machines in precise mathematical formalism. If you are looking for something even more formal, have a look at this Coq formalization of Turing machines.


Could an artificial neural network algorithm be expressed in terms of map-reduce operations? Could an artificial neural network algorithm be expressed in terms of map-reduce operations? I am also interested more generally in methods of parallelization as applied to ANNs and their application to cloud computing.

I would think one approach would involve running a full ANN on each node and somehow integrating the results in order to treat the grid like a single entity (in terms of input/output and machine learning characteristics.) I would be curious even in this case what such an integrating strategy might look like.

Yes it can, and has been. In the paper Map-Reduce for Machine Learning on Multicore they discuss using the Map-Reduce paradigm for several common ML algorithms including ANNs.


Are there any problems that are easy to compute but hard to verify? Assuming P $\neq$ NP, NP-complete problems are "hard to solve, but have answers that are easy to check."  Does it make any sense to consider the opposite, that is, problems for which it's easy to compute a correct answer, but hard to verify an arbitrary purported solution?

I think such a problem would imply either:

Exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.
Some "correct" answers are easy to compute, but others are difficult to find.

If you are fine with artificial problems, you can make plenty of them.  Here are a few:

Given a positive integer n in unary, answer a satisfiable 3CNF formula in n Boolean variables.
Giving one satisfiable 3CNF formula is easy, but deciding whether a given 3CNF formula is satisfiable or not is 3SAT, a well-known NP-complete problem.
There is no input.  Just answer a Turing machine which halts (when run with an empty input tape).
Giving one such Turing machine is easy, but whether a given Turing machine halts or not is undecidable.

Added: By the way, I do not think that what you wrote in the last paragraph holds:

  I think such a problem would imply exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.

If the problem has one solution, then indeed checking an answer is no harder than computing the correct solution.  However, if the problem has one easy solution and one difficult solution, then you cannot compute all the solutions efficiently.  Here is one such problem (which is very artificial):

Given a Turing machine M, answer one of the following statements that is true: “M halts on empty input tape,” “M does not halt on empty input tape,” and “M is a Turing machine.”
Giving one solution is easy: you can always choose “M is a Turing machine.”  However, whether a given answer is correct or not is undecidable.  Note that in this problem, there are only two solutions for each instance.


Reduction from $L_{nonuniversal}$ to $L_{finite}$ As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly.

Given are two languages $L_{finite}$ and $L_{nonuniversal}$:

$L_{finite} = \{\langle M \rangle \mid \vert L(M) \vert < \infty \}$

$L_{nonuniversal} = \{\langle M \rangle \mid L(M) \neq \{0,1\}^* \} $

I'm trying to proof the following reduction: $ L_{nonuniversal} \le_T L_{finite} $

Given $M$ let $M'$ be the Turing Machine that on input $w$ simulates $w$  on $M$. It then takes $w$ after $M$ halted and removes it from its tape and replaces it with a static word $v$ (let this be "1" for example, anything that is $\neq \{0,1\}^*$).

Give $M$ and $M'$ to the $finite$ oracle and return its answer.

I'm trying to show here that if $w$ can only be a static string, then it's $\in finite$.

For brevity, denote $L_{finite}, L_{nonuniversal}$, respectively, as $L_f, L_n$. To establish a mapping from $L_n$ to $L_f$ we map $\langle\,M\rangle\rightarrow\langle\,N\,\rangle$, where $\langle\,N\,\rangle$ is defined by

N(x) =
   for s = epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... //i.e., the standard order
      run M on s
      if M(s) = accept and s = x
         return accept

Now look at the behavior of this mapping:

If $\langle\,M\,\rangle\in L_n$ there will be some string in $\{0,1\}^*$ which is not accepted by $M$. Let $z$ be the first such string in standard order. Then $N$ will accept all and only those strings $y$ which are earlier in order than $z$ so $L(N)$ will consist of only those $y$s and so will be finite, i.e., $\langle\,N\,\rangle\in L_f$.
Similarly, if $\langle\,M\,\rangle\notin L_n$, then $L(M)=\{0,1\}^*$ so $M$ will accept every string and consequently $L(N)=\{0,1\}^*$, an infinite language, so $\langle\,N\,\rangle\notin L_f$.

These two observations establish the reduction we need.


Is type inference done by an interpreter static or dynamic? Type inference can be done by a compiler, and in such cases, type inference is static.

Type inference can also be done by an interpreter. An interpreter does the jobs of both compilation and execution. So is type inference done by an interpreter static or dynamic?

This question is an example that motivated my question Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language? at a more general level.

Typically , type inference in interpreted languages happens after parsing (because type inference works on ASTs) but before interpretation (= execution). Both compilers and  interpreters have a phase distinction between type inference, and the execution. The former happens strictly before the latter.

BTW, it's wrong to say that an "interpreter does the jobs of both compilation and execution". An interpreter does not do compilation.

A compiler is a meta-program that takes as input a program and outputs another program (the executable). It is this output that is executed.
An interpreter is a meta-program that takes as input a program and executes it.

Maybe the following picture clarifies the issue.


The VC dimension when the samples are fixed The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the hypothesis that scores best on the training-samples. If the VC dimension is sufficiently small and the number of samples is sufficiently large, then this best hypothesis will also perform probably-approximately-well on any set of test-samples drawn from the same distribution. Specifically, if the VC-dimension is $D$ and the number of samples is at least:
$$
N := \Theta\bigg(\frac{D + \ln{1\over \delta}}{\epsilon}\bigg)
$$
then, with probability at least $1-\delta$, the test-error will be at most $\epsilon$.

I am interested in the following alternative setting. Instead of a probability distribution, we have a ''fixed'' set of samples, determined by an adversary. We pick half of these samples at random, calculate the best hypothesis on this half, and then test it on the other half.

MY QUESTION IS: is it possible to use the VC dimension in the second setting? I.e, is there a formula, similar to the one above, that relates the total number of samples in the population, the probability of learning, and the learning error?

Suppose were in the realizable model, i.e. we want to learn some $f^*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$.

Let $M(\epsilon,\delta)$ be the minimal number of samples required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any distribution $\mathcal{D}$ over the sample space $\mathcal{X}$, we can treat this case as a uniform distribution with finite support $S=\left\{a_1,...,a_n\right\}$ (picked by the adversary). The learner picks a  set $T\subseteq S$ of $n/2$ samples (chosen uniformly at random), and chooses any consistent hypothesis $h$ (relative to $T$).

There are two issues which prevent us from directly using the known bounds on $err(h)$.

The first is that we are only interested in the error on the set $S\setminus T$, i.e. the training and test samples are not independent. This will add an extra $2$ factor to the bounds on $err(h)$, since:

$err(h)=\Pr_{x\sim\mathcal{D}}\left(h(x)\neq f^*(x)\right)=
\Pr\left(h(x)\neq f^*(x) | x\in T\right)\Pr(x\in T)+\Pr\left(h(x)\neq f^*(x) | x\notin T\right)\Pr(x\notin T)$.

In this case we have $\Pr(x\in T)=\Pr(x\notin T)=\frac{1}{2}$, and $\Pr\left(h(x)\neq f^*(x) | x\in T\right)=0$ ($h$ is consistent with $T$). So we get $err(h)=\frac{1}{2}\Pr\left(h(x)\neq f^*(x) | x\notin T\right)$, or equivalently $\Pr\left(h(x)\neq f^*(x) | x\notin T\right)=2err(h)$, where the left hand side is the probability that we wish to bound.

The second issue is caused by the fact that we don't allow repetitions while picking $T$ (the usual model treats each training sample as chosen independently from the distribution $\mathcal{D}$). To avoid this issue, the learner could choose $T$ by taking $m$ independent samples form $\mathcal{D}$, such that with high probability we see at least $\frac{|S|}{2}$ samples. This can be easily done by picking $m\approx |S|$, and conditioning on the event that we saw at least half of $S$, we can use the regular bounds on $err(h)$ for sample size $\ge|S|/2$.


Method to recognize abstract objects such as hand-drawn objects? My research is in the area of Document Image Analysis. To be specific, the topic of my thesis is to automatically recognize and index characters in a set of hand-drawn objects, e.g. given a volume of comics --> how to localize, recognize then index the characters in it (e.g. return "Lucky Luke" position in some random volume).

First thing first, before I can work on the indexing part, I must have some reliable system to recognize the interested characters. After some months working on it, I find the recognition is extremely hard, because the drawings are some time very "abstract".

For normal face recognition, there are a lot of researches on it, thus we have Haar-like features, biometrics features, etc. For normal photograph objects, we may use e.g. SIFT/SURF, or other strong features for the purpose of object recognition.

But in cartoons or comics, we may extract so few or zero feature(s) following the traditional approaches. Human visual interpretation system is amazingly effective in recognize such abstract objects (e.g. only with 4 lines and 2 curves, we still recognize the familiar character).

So I think the solution must be somewhere in the understanding how human can interpret such a set of line strokes as a meaningful object. Once we understand it we can try to "teach" the computer the same way.

Thus are there some good approaches in the terms of recognition of abstract objects such as drawn comic objects? (I searched for some but they're not so relevant). Thanks.

It sounds like you're looking for shape matching techniques.  Sven Loncaric's well-cited survey paper "A Survey of Shape Analysis Techniques" from 1998 can be found here.

In 2002, Belongie, Malik and Puzicha proposed a similarity measure between two shapes based on

  solving for correspondences between points on the two shapes, then
  using the correspondences to estimate an aligning transform.

David Marr's book 'Vision', particularly §3.6 and chapter 5, also provides some background about the correspondence between shape recognition in human visual systems and computers.


Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a hyperplane to partition this point cloud into two parts, $S$ and $S^c$, in order to maximize $\sum_{i\in S} X_i$. Are there any efficient ways to do it?

Any advice would be greatly appreciated. If this cannot be solved efficiently, do there exist a good approximation algorithm?

The special case of your problem in which the points are in $\{-1,1\}^n$ and the values are $\pm 1$ is known as Maximum Agreement for Halfspaces. When talking about approximation, we want a positive objective function, and in this case it is convenient to ask for the number of correctly classified points. A point is correctly classified if either its value is $+1$ and it belongs to $S$, or its value is $-1$ and it belongs to $S^c$.

A trivial $1/2$-approximation algorithm just picks any halfspace and chooses either the halfspace or its complement. One of these satisfies at least half the constraints. Guruswami and Raghavendra showed that no better polynomial time approximation algorithm exists unless $\mathsf{P}=\mathsf{NP}$.

In practice you might be able to use some heuristics, but these of course don't provide any guarantees in the worst case.


Storing Specific data on DB Table(s) I have an Excel with 40columns and 20k rows, and i have to store it in a database but i cant figure the best approach for it, the excel format is like this:

This table has 30 columns for days, then 11 columns for the next 11 weeks and then 9 columns for the next 9 month, in resume the first month is in days the next 3 months are in weeks and the rest of the year is in months.

Each column has the number of pieces that i need to produce certain product in that span of time.

Part number | 1/1/2018 ||||| 30/1/2018 | Week6 ||| Week16 | Month4 ||||||Month12
PART1             2             5          10        12        40          50
PART2             3             4          13        11        50          70
PART3             4             3          13        15        60          60
PART4             1             3          16        12        40          30

This Excel file has to be pasted in to a datagridview and then save it in a DB,
should i use 1 table or more? what shold be my table design to store this data?

In my mind when you start using a "DB" I'm assuming that you mean a relational/SQL database, and then the design of how the information is stored might change entirely.

It seems like you're using this Excel file to track a master production schedule for some kind of parts manufacturing, so it's how many parts you need, and when you need them by.

I'm not sure it makes sense to have multiple time scales in the same table for that purpose. So my reflex would be to say, we should create a table that stores information about, the date, how many parts need to be produced on that date, and which part needs to be produced.

CREATE TABLE production_schedule (
    prod_date date,
    part_no   int,
    part_qty  int
);

Then if you need to build reporting or gather the information about how much in a week, a month, six months, or a year. You could do that with queries when you need that information or you could create views that are based on such queries.

For example, a query like the following would return the total amount of parts to be created in January 2018.

SELECT SUM(part_qty) FROM production_schedule WHERE prod_date BETWEEN '01/01/2018' AND '31/01/2018';

Hopefully, this helps you understand the way you should think about creating a database to solve your problems, and perhaps a verbatim transfer of the information isn't the best solution.

It can help when getting started to think of databases as spreadsheets because they store information in a way that can be thought of as "column and row". The fact that you can store information in them and also ask sometimes simple and sometimes complicated questions of them can throw off people who are new to working with databases.


Is The Following Language Regular? Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$.

$$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$

Assume that $L_{1}$ is regular and $L_{2}$ is context-free. The language $A(L_{1},L_{2})$:

is always a regular language
is always not a regular language
can sometimes be a regular language
cannot be context free

They say that the correct answer is 1.

Hint: Take a DFA for $L_1$. Check which states are reachable from the initial state via a word in $L_2$. Check from which states a final state can be reached via a word in $L_2$.


How to build 4 codewords with a code distance of 5? I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to achieve this code distance for the 6 possible pairs from the 4 codewords available(of any bit length). I named, for example, codewords u, v, w, & x so d(u,v) = d(u,w) = d(u,x) = d(v,w) = d(v,x) = d(w,x) = 5. The code words must be in binary format i.e 00100 10011. I considered a code length of 10 to achieve this but still struggling to find a solution.


Minimum Weight Directed Subgraph ensuring all pairs reachability? After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an algorithm for it. I couldn't find anything in Google or Google Scholar.

Given a directed graph $G=(V,E)$ with a weight for each edge given by $w(e)$, find a subset $S \subseteq E$ of minimum cost (sum of weights) such that for every pair $u,v \in V$ of nodes, there is a path from $u$ to $v$ that traverses only edges in $S$.

For instance:

A--2->B
^     |
|2    |2
|     v
C--1->D
 <-3--

In the example, there is an edge from C to D of cost 1 and the opposite direction of cost 3. The solution here would be the edges CA, AB, BD and DC.  This solution has cost 9.

Any variation of Prim or Kruskal fails on this problem, and I can't see any other algorithm that I could modify to work here. Also, I can't come up with any algorithm (I'm starting to suspect its NP-complete, but I am still looking for a reduction).

Can anyone tell me if this is indeed proven NP-complete or if there is a polynomial-time algorithm for this?

This problem is a generalized version of the famous Minimum Spanning Strong Subdigraph or MSSS [1]. This problem is NP-hard and there are several heuristic algorithms for it. You may look at the reference given in this solution and the related papers to find out more about this problem.

Note that this problem itself is a simplified version of Minimum Equivalent Graph of a Digraph [2]. Therefore, there are some algorithms that you can use as a heuristic for this problem.

[1] Bang-Jensen, Jorgen, Jing Huang, and Anders Yeo. "Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs." SIAM Journal on Discrete Mathematics 16.2 (2003): 335-343.

[2] Martello, Silvano, and Paolo Toth. "Finding a minimum equivalent graph of a digraph." Networks 12.2 (1982): 89-100.


Reversing topo-order of the original graph instead of the topo-order of the transposed graph? (Note that my question is different from this one, I understand why we have to do a dfs on a reversed graph, I want to understand why we can't reverse the topological order instead of transposing the graph.)

In Kosaraju's algorithm, it is stated to compute the transposed graph and apply topological sort on it. I understand why this is necessary.

What I don't understand is the necessity to actually compute the transposed graph. Can't we just apply the topological sort algorithm on the original graph and use the resulting list in reverse order?

In Dasgupta,Papadimitriou, Vazirani, one can read

  There is not an easy, direct way to pick out a node that is guaranteed
  to lie in a sink strongly connected component.

I am having trouble to see why. If I apply a explore on any node of the following graph, the first finished node will be one of inside a sink strongly connected component.

Wikipedia's description of the algorithm seems to confirm this. The first DFS prepends instead of appending.

Can someone show an example (if any) where using the reversed topological order of the original graph instead of the topological order of the transposed graph is wrong?

It may work for the graph you give, but not for all graphs.  Consider a graph with 3 vertices, A, B, and C.

$A \rightarrow B, C$

$B \rightarrow A$

Search on A, exploring B before C, B finishes first but is not in a sink.

Also, note that for the Wikipedia article, the search is on incoming edges, not outgoing, which is why it doesn't need to explicitly transpose the graph.


is it possible to know if a language is regular if its equivalence classes are finite? i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.

1)suppose we have some language L over $\Sigma$, can we know if L is regular if all of it equivalence classes of relation $R_L$ is finite?

2)and what about L*? is it finite? i mean the cardinality is infinity(alef), but can it be made into a finite language?

Edit: my question is about Myhill–Nerode relation

i am curious about those and your input would really help me understand more about it

thank you very much!

One of the main results of Myhill–Nerode theory is that a language is regular iff its Myhill–Nerode relation has finitely many equivalence classes. You can find a proof in many online resources. In particular, if all equivalence classes of the Myhill–Nerdoe relation of a language are finite, then it must have infinitely many equivalence classes, and so be non-regular.

The language $L^*$ is finite in two cases: if $L = \emptyset$ or if $L = \{\epsilon\}$. In any other case it is infinite.


What does "Kan" mean in "Kan operations"? I'm studying Cubical Type Theory and I see the word "Kan operations" (ref1, ref2, ref3, and there are many more), which is related to "adding a cap to a tube" (can be also explained as "given a path between a and b, and two paths that are between a and c/b and d respectively, we can use Kan operations to get a path between c and d").

I wonder if there's any references that can explain where this "Kan" word come from -- what does it mean? Is that "Kan extensions" in Category theory?

Kan operations are likely named after Daniel M. Kan, in analogy to concepts such as Kan extensions, Kan complexes, Kan fibrations, Kan condition, and many more. Kan also introduced adjoint functors.


How to cluster images based on meta-information in tags Context and Motivation

I have researched online for an algorithm (independent of a programming language AND in the context of Machine Learning) that accepts images as inputs with the expectation that individual images contain tags in the form of semi-structured information (for example, in the JSON format) that identify physical objects inside each image.

My goal is to find a clustering algorithm that will cluster objects based on common occurences of strings (i.e. physical objects described by a word, for example 'tree', 'mountain', 'airport' etc) contained in the tags about the images AND NOT on the input features of individual images contained in the pixels.

Question

My question is a binary question (Yes / No) - has such an algorithim been studied in published papers? If yes, can you refer me to a source or a list of sources that explores, explains, discusses, codes AND/OR contains instructions on how to implement the algorithm?

Input:

A set of images with semi-structured tags identifying physical objects in each indiviual image.

Output:

A set of clusters where images are grouped based on commonly occuring objects in the images.

Thanks and appreciation in advance.

Yes, this has been studied, but the images seem to be completely irrelevant.

What you have is a set of texts, and you want to cluster them based on similarities.  You simply want to do text clustering.  A very simple way to start is to create a vector that represent each of the words.  Suppose that you have 1000 words.  Sort them, and you have a 1000 dimensional vector.  Now, each text (metadata) is represented by a vector with a 1 in position $i$ if the $i$th word is in the text and 0 otherwise.

Do clustering on these vectors as you normally would, you can easily start of with $k$-means clustering.


If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.

By the definition of $\leq_m$ we can construct the following statement,

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

This is where I'm stuck, I want to say that since we have such computable function $f$ then it'll only give us the mapping from A to B if there is one, otherwise it wont.

I don't know how to phrase this correctly, or if I'm even on the right track.

As Dave said, it follows from a simple logical equivalence: $p \leftrightarrow q$ is the same as $\lnot p \leftrightarrow \lnot q$. Now put $p= w\in A$ and $q = f(w) \in B$.

$A \leq_m B$ means there is a total computable $f$ s.t. for all $w$,

  $w \in A \leftrightarrow f(w) \in B$.

By the argument above, this is the same as

  $w \notin A \leftrightarrow f(w) \notin B$.

Or equivalently

  $w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$.

And therefore, the same $f$ shows that $\bar{A} \leq_m \bar{B}$.


Largest set of vertices that is larger than its set of neighbors I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$.

For every subset $X' \subseteq X$, they define

$$f(X')=\bigcup_{i \in X'} \{j \in Y| (i,j)\in E\}.$$

In other words, $f(X')$ is the set of neighbors of vertices in $X'$.

Then they define:

$$ X^+ = \arg \max_{X' \subseteq \{2,3,...,n\}\ s.t.\ |X'|\geq|f(X')|}\{|X'|\}$$

i.e., $X^+$ is a largest subset of $\{2,3,...,n\}$ such that $X^+$ is at least as large as the set of its neighbors in $Y$ (i.e., the largest subset such that $|X^+| \ge |f(X^+)|$).

And then they do some stuff with this $X^+$.

MY QUESTION IS: Can this $X^+$ be found in polynomial time?

The authors do not prove that it can, but this is implied by the paper (otherwise the algorithm itself cannot be polynomial). Maybe it is so obvious that only I haven't seen this?

EDIT: The following similar problem can be solved easily:

Find the largest set of vertices in X with less than |Y| neighbours.

Solution: find a $y \in Y$ with a minimal number of neighbours in $X$. Return the set that includes all vertices in $X$ except $y$'s neighbours.

What about the following similar problem?

Find the largest set of vertices in X with less than |Y|/2 neighbours.

Consider the following problem.

  Find $X''$ such that $|X''| = k$ and $|f(X'')| = m$

If it was P then so would set cover: fix $m = |Y|$ and iterate over all $k \in \{1, \dots, |X|\}$ to find a minimum.

Let's call this problem $\text{exact}(G, k, m)$ and let's call your problem $\text{largest}(G)$.

Let $G(X, Y, E)$ be any bipartite graph. Let $G^1$ be a graph with one additional vertex in $X$, not connected to anything. Let ${_1}G$ be a graph where for every vertex of $X$, a new vertex is added to $Y$ and the two are connected. Let ${^1}G$ be a graph where for every vertex of $Y$, a new vertex is added to $X$ and the two are connected. Let ${_k^l}G^i = ({_k}({^l}G))^i$ be these transformations applied repeatedly. Note the order.

$G^i$ will be used to artificially raise $|X^+|$ and therefore $|f(X^+)|$. ${_k}G$ will be used to weight down vertices $v$, so we can control whether $v \in X^+$ even if $f(v) \subset f(X^+)$ in $G$. ${^l}G$ will be used to prioritize larger $|f(X^+)|$.

Say $X^+ = \text{largest}(G^i)$. This implies that $\text{exact}(G, |X^+|-i, |f(X^+)|)$, because you know that the $i$ new vertices in $X$ will be used and thus $|X^+|$ old vertices have a neighborhood of $|f(X^+)|$ old vertices. Similarly $X^+ = \text{largest}({_k}G)$ implies $\text{exact}(G, |X^+|, |f(X^+)|-k|X^+|)$.

To find $\text{exact}(G, k, m)$, let $X^+_i = \text{largest}({_M^i}G^{(mi+k)M+(m-k)})$ for sufficiently large $M$ (say, $M = |X|+|Y|$).

If $|X^+_0| < kM + (m-k) + k$ then $\text{exact}(G, k, m)$ is false.
If $|f(X^+_i)| = (mi+k)M+m$ then $\text{exact}(G, k, m)$ is true. Note that if $\text{exact}(G, k+ix, m-x)$, then $|f(X^+_i)|$ could also have the value $(mi+k)M+m-x$.
Raise $i$ until $\forall x>0, \neg \text{exact}(G, k+ix, m-x)$ (you can jump directly to $i=|X|$). Then $|f(X^+_i)| = (mi+k)M+m$ if and only if $\text{exact}(G, k, m)$.


Is It possible to change the side of 0 and 1 in Huffman tree? When we are constructing the Huffman tree to get the Huffman codes, Is it possible to give "1" to left side and "0" to right side rather than giving "0" to left side and "1" to right side of the tree?

You can assign the $1$ and $0$ as you like, but be consistent. Only your code change, i.e. a 1011 becomes a 0100.


How does a File System handle an internal edit to a file? When you edit information in a file, but you add in more information than was already present, how does the file system handle it without an overflow into the next section of the file?

Here's an example. Consider having statements 1-12 in a 512-byte block, and you had statements 13-24 in the next 512-byte block. [Image 1] These blocks are both part of the same file. If you edited the first block, so you add another few New Statements [Image 2] past statement 12, this would overflow into the next block (statements 13-24). How would this condition be handled? Through shifting all the statements ahead of the added statement forward, or putting the new edit in a completely separate new block?

(sorry if the pictures or wording are a bit improper; this is my first time)

Filesystems typically don't handle internal edits to files as you describe them.  When you edit a program file, a text editor will pull the whole file into memory, allow you to make modifications to a buffer and then write the whole thing back out to disk.  Actual file I/O operations are usually quite limited by the operating system, e.g. overwrite existing file contents, truncate the file to a smaller size discarding what's beyond EOF, and appending to the file.

Text editors manage the business of allowing arbitrary insertion and deletion of lines and blocks of text.  These programs use an assortment of data structures, from arrays of lines to gap buffers to more elaborate structures, depending on the editor.  An old Blogspot article describes how a few popular text editors work internally; I commend you to it and to the source code of the many open-source text editors available if you wish to learn more.


The time complexity of finding the diameter of a graph What is the time complexity of finding the diameter of a graph
  $G=(V,E)$?

  ${O}(|V|^2)$
  ${O}(|V|^2+|V| \cdot |E|)$
  ${O}(|V|^2\cdot |E|)$
  ${O}(|V|\cdot |E|^2)$

The diameter of a graph $G$ is the maximum of the set of shortest path distances between all pairs of vertices in a graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.

I assume you mean the diameter of $G$ which is the longest shortest path found in $G$.

Finding the diameter can be done by finding all pair shortest paths first and determining the maximum length found. Floyd-Warshall algorithm does this in $\Theta(|V|^3)$ time. Johnson's algorithm can be implemented to achieve $\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$ time.

A smaller worst-case runtime bound seems hard to achieve as there are $\cal{O}(|V|^2)$ distances to consider and calculating those distance in sublinear (amortised) time each is going to be tough; see here for a related bound. Note this paper which uses a different approach and obtains a (slightly) faster algorithm.


Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL Assuming $L$ is defined as follows:

$$ L = \{ 0^n1^{n^2} | n \ge 0 \} $$

I'm trying to either prove/disprove whether $L$ is CFL or not.

My intuition tells me its not CFL since I cannot express the power $n^2$ by itself using CFL, but I'm having trouble proving so using the pumping lemma.
Also, I failed to create any such PDA (which my intuition says its impossible).

Let $h\colon \{0,1\} \to \{0\}$ be the homomorphism given by $h(0) = \epsilon$ and $h(1) = 0$. If $L$ were context-free, so would $h(L) = \{ 0^{n^2} : n \geq 0 \}$ be. Since $h(L)$ is a unary language, it would be regular. However, a unary language is regular iff it is eventually periodic, which it isn't. Therefore $L$ cannot have been context-free.

More generally, if $L$ is context-free then:

The set of lengths of words in $L$ is eventually periodic.
The set of number of occurrences of a symbol in $L$ is eventually periodic.

The most general statement of this kind is Parikh's theorem.


Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $[i, j]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we use a modification of the rolling hash?

The following is a similar problem to my question. In it the string was given in a compressed form. Example: if the string is "aaabccdeeee" then the compressed form is:

3 a
1 b
2 c
1 d
4 e

The data was stored in an str[] array as :

str[] = [{'a','3'}, {'b','1'}, {'c','2'}....]

Note that hashing was used in the solutions, which checked if the given substring is a palindrome or not. Given a substring of string $S$ as $(i, j)$, they computed the hash of substring $[i, (i + j) / 2]$ and the reverse hash of substring $[(i+j+2)/2, j]$ and checked if they were equal or not. So if they wanted to check if in string S = "daabac" whether substring $[1, 5]$ is a a palindrome or not, they computed the following :

h1 = forward_hash("aa")
h2 = reverse_hash("ba")
h1 == h2

Code for the hashing concept

The hash precomputation was done as follows:

/* Computing the Prefix Hash Table */
pre_hash[0] = 0;
for(int i = 1;i <= len(str); i++)
{
    pre_hash[i] = pre_hash[i - 1] * very_large_prime + str[i].first;
    pre_hash[i] = pre_hash[i] * very_large_prime + str[i].second;
}

/* Computing the Suffix Hash Table */
suff_hash[0] = 0;
for(int i = 1;i <= len(str); i++)
{
    suff_hash[i] = suff_hash[i - 1] * very_large_prime + str[K - i + 1].first;
    suff_hash[i] = suff_hash[i] * very_large_prime + str[K - i + 1].second;
}

And then the hash was computed using the following functions :

/* Calculates the Forward hash of substring [i,j] */
unsigned long long CalculateHash(int i, int j)
{
    if(i > j)
        return -1;
    unsigned long long ret = pre_hash[j] - POW(very_large_prime, [2 * (j - i + 1)])*pre_hash[i - 1];
    return ret;
}

/* Calculates the reverse hash of substring [i,j] */
unsigned long long CalculateHash_Reverse(int i, int j)
{
    unsigned long long ret = suff_hash[j] - POW(very_large_prime, [2 * (j - i + 1)]) * suff_hash[i - 1];
    return ret;
}

What I am trying to do

I am looking for a general approach to the above concept. Given a Pattern $P$, I want to check if the pattern $P$ is present in a string $S$. I know the index $i$ to check where it may be present. And I also know the length of pattern $P$ represented as $|P|$. In short I want to check if hash of $S[i, i + |P|]$  and hash of $P$ match or not in $O(1)$ using some form of precomputation on $S$. (Ignoring the time taken to compute hash of $P$ else it would be $O(1+|P|)$.)

Yes, you can solve your problem, roughly speaking, by precomputing prefix sums.

In particular, if you are willing to do $O(n)$ precomputation and to use $O(n)$ space, we can solve your problem, for most standard rolling hashes.  We just need the rolling hash to have one extra property, the inverse property.  Most rolling hashes do have this property, including the well-known Rabin-Karp rolling hash.

Let me explain the details, below.

Some notation: let $S[i..j]$ denote the substring of $S$ from index $i$ to $j-1$ (note: it doesn't include index $j$; it is a substring of length $j-i$).  Let $H(S[i..j])$ denote the rolling hash of that substring.

The intuition

Imagine that we used a very simple hash, which is just the sum of the bytes modulo 256:

$$H(S[i..j]) = S[i] + S[i+1] + S[i+2] + \dots + S[j-1] \bmod 256.$$

This is a crummy hash function (it has lots of collisions), but let's go with it, since the purpose is just to get some intuition.  This is a rolling hash; given the hash of a prefix of the string, it is easy to extend it by one more byte (just add that byte to the hash value you've got so far).

Now with this hash function, we could easily solve your problem.  During the precomputation, we'd fill in an array $A[]$ so that $A[j] = S[0] + S[1] + \dots + S[j-1] \bmod 256$ for each $j$; this can be done in $O(n)$ time.  Now, we can compute $H(S[i..j])$ via the simple relation

$$H(S[i..j]) = A[j] - A[i] \bmod 256.$$

This can be computed in $O(1)$ time, given the precomputed array $A$.

Of course, you'd never use this in practice, because it's such a crummy hash function.  But the same idea can be generalized to work with many other rolling hash functions, which you would want to use. (Intuitively, that's because they are based upon a binary operation that is associative and has an inverse, which is all you need for this trick to work.)  I'll describe the details next.

The inverse property

All rolling hashes have the following property:

The accumulation property: Given $H(S[i..j])$ and $S[j]$, we can compute $H(S[i..j+1])$.

We need one additional property from the rolling hash:

The inverse property: Given $H(S[i..j])$ and $H(S[i..k])$, where $j < k$, it should be possible to derive $H(S[j+1..k])$.

Many standard rolling hashes do have this inverse property.  For instance, the Rabin-Karp rolling hash has the inverse property.  The same is true for hashing with cyclic polynomials (Buzhash).

How to use the inverse property for your problem

Create an array $A[]$ of $n$ elements.  During precomputation, we will fill in the elements of $A$ so that $A[j] = H(S[0..j])$.  This precomputation can be done in $O(n)$.

Now, at some later point, you would like to compute the rolling hash of $S[i..j]$, i.e., to compute $H(S[i..j])$.  How do you do that?  It turns out it is easy.  First, look up $H(S[0..i])$ and $H(S[0..j])$ using the array; this involves reading the value of $A[i]$  and $A[j]$.  Next, use the inverse property to compute $H(S[i..j])$ from these two values.  Done!  That's all there is to it.


How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction? As the title states, how do you prove that $A$ is productive? With $W_{x}$ I mean the set of points in which the turing machine with index $x$ halts.

The standard approach that I follow is functional reduction: first I construct a partial recursive function $\psi(x,y)$. Then through the s-m-n theorem I build a partial recursive function $\varphi_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive. Then I proceed to show that $\overline{K}$ reduces to the set I'm studying through $g$. The problem is that in this set the condition includes the index of the partial function ($x$) so I don't know how to construct a suitable $\psi$ function. As you can see from the appendix, I can't reach $g$ in $\psi$, so I can't build $g$ to behave like a member of the $A$ set.

How can I overcome this problem?

APPENDIX: example of proof with functional reduction

Let's show that $B = \{ x\in \mathbb{N} | W_x = \emptyset \}$ is productive.

We do this by proving that $\overline{K}$ reduces to $B$, so equivalently we can show that $K$ reduces to $\overline{B} = \{x\in \mathbb{N} | W_x \neq \emptyset \}$.
Consider the function:
$$
    \psi(x,y) = \left\{\begin{array}{lr}
        1, & \text{for } x \in K\\
        \uparrow, & \text{otherwise} \\
        \end{array}\right\}
$$

(Notice that $\psi$ is computable since $K \in RE$).
We can now build $\varphi_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive (s-m-n theorem). At this point:

$x \in K \implies \forall y\in \mathbb{N}. \varphi_{g(x)}(y) \downarrow \implies W_{g(x)} = \mathbb{N} \implies W_{g(x)} \neq \emptyset\implies g(x) \in \overline{B}$.

$x \notin K \implies \forall y\in \mathbb{N}. \varphi_{g(x)}(y) \uparrow \implies W_{g(x)} = \emptyset\implies g(x) \notin \overline{B}$.

So $K$ reduces to $\overline{B}$ thorugh $g$: $B$ is productive. $\square$

You likely need to exploit the second recursion theorem, which states that for any total recursive function $f$ there is some $n$ such that $\varphi_n = \varphi_{f(n)}$.

Given any $k$, using s-m-n you can first construct $f_k$ as follows, where $\#(\ldots)$ stands for "some index of".
$$
f_k(x) = \#\left(y \mapsto
   \begin{cases}
   0 & \mbox{if } y \leq x \\
   \varphi_k(k) & \mbox{otherwise}
   \end{cases}
\right)
$$

This is recursive total, since it always returns an index (the fact that the index is for a partial function is irrelevant). So, by the second recursion theorem, there must exist $n_k$ for which $\varphi_{n_k} = \varphi_{f(n_k)}$.

By examining the proof of the second recursion theorem, we can also note that $n_k$ is effectively computable from $k$, that is there is a total recursive function $g$ such that $\varphi_{g(k)} = \varphi_{f(g(k))}$.

Let's verify that $g$ m-reduces $\bar K$ to your set $A$.

Assume $k \in \bar K$, and let's prove $g(k) \in A$. The latter means $W_{g(k)} = [0..g(k)]$, which is true because
$$
\varphi_{g(k)}(y) = \varphi_{f(g(k))}(y) =
\begin{cases}
   0 & \mbox{if } y \leq g(k) \\
   \varphi_k(k) & \mbox{otherwise}
   \end{cases}
= \begin{cases}
   0 & \mbox{if } y \leq g(k) \\
   \uparrow & \mbox{otherwise}
   \end{cases}
$$

Now, assume $k \notin \bar K$, and let's prove $g(k) \notin A$. The latter means $W_{g(k)} \neq [0..g(k)]$, which is true because

$$
\varphi_{g(k)}(y) = \varphi_{f(g(k))}(y) =
\begin{cases}
   0 & \mbox{if } y \leq g(k) \\
   \varphi_k(k) & \mbox{otherwise}
   \end{cases}
$$
Since $\varphi_k(k)\downarrow$, we have that $W_{g(k)} = \mathbb N \neq [0..g(k)]$

As a thumb rule, when you are defining a recursive function $f=\varphi_i$ and you need to use its own index $i$ in the definition of the function itself, you need the second recursion theorem.

From a more practical point of view, the second recursion theorem allows one to program in a programming language featuring a function getMyOwnCode() : String which returns the whole source code (the index) of the program calling the function.


High Dimensional Data Structures I have a 20-dimensional dataset, with a large amount of data points. I would like to have each dimension discretized into bins. Per bin, I would like to be able to access two neighbours per dimension (i.e. +1 and -1 per dimension). Basically I want to be able to easily access 2*d (where d is the dimensionality) neighbours. For lower dimensions, this would be quite easy to do using a multidimensional array (i.e. for point data[0][1][2] I would access its neighbours data[0][1][3] and data[0][1][1] for the third dimension). However, when this approach is scaled up to higher dimensions, memory becomes an issue.

What kind of data structures would be suitable to use, where the most important criterium is the quick and easy access to its +1 and -1 neighbours?

I would suggest you to use a hierarchical K-means, or a hierarchical vocabulary tree approach. For example:

http://gecco.org.chemie.uni-frankfurt.de/hkmeans/H-k-means.pdf
http://www.vlfeat.org/overview/hikm.html

CVPR Paper with application:
http://www.vis.uky.edu/~stewe/publications/nister_stewenius_cvpr2006.pdf

FLANN also has some kind of hierarchical capabilities.


What is the complement of the language with all ucv with u ≠ v? If $L = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 \neq w_2\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 = w_2\}$ and he said that we can ignore $c$ and it's not in $\Sigma$ of language $L$. but I think $c$ should be in $\Sigma$ of language $L$ and the complement mentioned above is wrong based on definition of complement that is $\{a,b,c\}^* \backslash L$. which answer is right?

Based on transition relation of pushdown automata where is maping from $(Q\times (\Sigma \cup \{\lambda \}) \times \Gamma) $ to $(Q \times \Gamma^*)$ so if we construct a pushdown automata for string $aabcabb$ for example here $c$ should be in $\Sigma \cup \{\lambda \}$.

The complement of a language $L$ over an alphabet $\Sigma$ consists, by definition, of all words over $\Sigma$ that are not in $L$. If you use this definition, you find out that $\overline{L}$ consists of all words of the form $wcw$ for $w \in \{a,b\}^*$ (like your friend said), as well as all words which contain either no $c$ or at least two $c$s.

The complement operation for languages, like the complement operation for sets, assumes an underlying universe. In the case of languages, the underlying universe is $\Sigma^*$, where $\Sigma$ is the alphabet that the language is defined over. You an think of languages in at least two ways:

A language is a pair consisting of an alphabet $\Sigma$ and a subset of $\Sigma^*$. We usually only explicitly mention the second part.
A language is a collection of "words" over some universal alphabet. We can think of the language as being over any alphabet which includes all the symbols appearing in the language.

While the more correct view is the first, the more practical view is the second. Therefore, whenever you take the complement of a language, you must make sure with respect to which alphabet the complement is taken. This can be done in at least two ways:

When you define the language, you also mention the underlying alphabet.
When you take the complement, you state with respect to which alphabet you are complementing it.

For example, you could say:

  Let $L$ be the language over $\{a,b,c\}$ given by $L = \{ w_1 c w_2 : w_1,w_2 \in \{a,b\}^* \text{ and } w_1 \neq w_2 \}$. What is the complement of $L$?

Or you could say

  Let $L = \{ w_1 c w_2 : w_1,w_2 \in \{a,b\}^* \text{ and } w_1 \neq w_2 \}$. What is the complement of $L$ (as a language over $\{a,b,c\}$)?


NP-hardness even with perturbations Consider the following problem, which can be called "2-SET-PARTITION":

  Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$, decide whether there exists a subset of indices $I\subseteq [n]$ such that:
  $\sum_{i\in I} b_i \geq S \geq \sum_{i\in I} a_i$.

It is easy to prove that this problem is NP-hard by reduction from PARTITION:

  Given an instance $p_1,\ldots,p_n$ of PARTITION, create an instance of 2-SET-PARTITION with:
  $\forall i\in[n]: a_i = b_i = p_i$. Obviously the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".

But, this proof considers only a small subset of the 2-SET-PARTITION --- the subset in which the two sets of integers are equal.  Theoretically, it could be that a "typical" instance of the problem is easy: it could be that there is a subset of instances, which includes all instances except a subset of measure zero, in which 2-SET-PARTITION can be decided in polynomial time. There are similar problems in which this is the case.

To prove that this is not the case with 2-SET-PARTITION, one can use the following reduction:

  Fix some vector of perturbations, $e_1,\ldots,e_n$, such that $\sum_{i\in [n]} e_i < 1/2$.
  Given an instance $p_1,\ldots,p_n$ of PARTITION, create an instance of 2-SET-PARTITION with:
  $\forall i\in[n]: a_i = p_i, b_i = p_i + e_i$. Here, too, it is possible to show that the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".

Intuitively, the second proof is much stronger than the first, because it shows that even arbitrary perturbations cannot make the problem easy.

MY QUESTIONS:

What is a term for this stronger NP-hardness concept, that is robust to perturbations?
What are some references showing proof techniques for this hardness concept?

If you allow arbitrary $e_i$, you are in muddy ground. Are your numbers real? No way to express them finitely, NP-whatever right out the window. Rational? The input size can blow up almost arbitrarily, again nothing relevant to prove.

Note that (for very good reasons) NP-hard and its ilk talk about the worst case complexity of the problem (that is well-defined, opposed to say avergage complexity; best-case essentially tells nothing in most interesting cases). That some proof gives just one particular hard case for particular sizes, while another gives a bevy of them, is irrelevant.


What's the Big O runtime of a DFS word search through a matrix? The problem is to try and find a word in a 2D matrix of characters:

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:

board =

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

Given word = "ABCCED", return true.

Given word = "ABCB", return false

Source: https://leetcode.com/problems/word-search/description/*

Solution:

static boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
                    return true;
                }
            }
        }

        return false;
    }

    private boolean search(char[][]board, String word, int i, int j, int index){
        if(index == word.length()){
            return true;
        }

        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
            return false;
        }

        visited[i][j] = true;
        if(search(board, word, i-1, j, index+1) ||
           search(board, word, i+1, j, index+1) ||
           search(board, word, i, j-1, index+1) ||
           search(board, word, i, j+1, index+1)){
            return true;
        }

        visited[i][j] = false;
        return false;
    }

Assume we use a DFS to recursively check each character's 4 neighbours. What would be the correct runtime? I've read various thoughts on this but nothing conclusive.

My thoughts:

We have to check every character in the MxN matrix, so that gives us at least M*N.

Then, for each character, we check in four directions for the length of the input string, so that would give us 4*len. But then for each neighbour we go to, we potentially check each of its neighbours too, but only if they haven't already been visited. This is where I get slightly confused and I'm not sure how to calculate the correct runtime for this.

(Edited question to add exact problem and solution)

The complexity will be $O(m*n*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string.

When we start searching from a character we have 4 choices of neighbors for the first character and subsequent characters have only 3 or less than 3 choices but we can take it as 4 (permissible slopiness in upper bound). This slopiness would be fine in large matrices. So for each character we have 4 choices. Total no. of characters are $s$ where s is the length of the input string. So one invocation of search function of your implementation would take $O(4^{s})$ time.

Also in worst case the search is invoked for $m*n$ times. So an upper bound would be $O(m∗n∗4^{s})$.


What are the gates used to implement Shor's algorithm? I understand theoretically how Shor's algorithm works, but I don't know what specific gates are used (or would be used) to implement it. What would the quantum circuit look like?

There are several correct answers to this question because there are several candidate sets available for use as a universal set of quantum operators and because there isn't an agreed upon best implementation for the primitives needed by Shor's algorithm. Different circuits will trade-off circuit-depth for ancillary qubits and vice versa.  Ultimately, the exact implementation is likely to depend on the architecture of the quantum computer.

What that in mind, you can probably find a version of the details you're looking for in Fast Modular Exponentiation Architecture for Shor's Factoring Algorithm by Pavlidis and Gizopoulos.  The exact circuit layout is lengthy and complex and probably too much for an answer here. The paper has lots of diagrams though and a quick scan should should provide you with a rough feel for the circuit construction. Unsurprisingly, the circuit makes heavy use of Hadamard gates and controlled phase-shift operators both to implement the inverse QFT and the modular exponentiation circuit.