Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within triplets). I have recordings of digits 0-9, recorded in each triplet position (i.e., I have 30 digits, 0 in 1st position, 0 in 2nd position, 0 in 3rd position, 1 in 1st position, 1 in 2nd position, etc...). This is for a homogenization task, i.e., a task for figuring out the signal to noise ratio (SNR) for each digit in each position so that the level of individual digits can be adjusted upward or downward to make them equally intelligible at a fixed noise level.

In the homogenization task, stimuli will be presented at 10 SNRs, and I want each digit in each position to be presented four times at each SNR, but in different triplets. Hence, I want 4 x 10 x 10 triplets total. (The four repetitions is somewhat arbitrary, but it's based on previous work, and 400 trials works out nicely with respect to the amount of time listeners will spend doing the task.)

There are 720 total triplets. I use Python, so it's easy to get the full list with:

all_triplets = list(itertools.permutations(np.arange(10),3))

I'm finding it very difficult to get a subset of 400 of the 720 possible triplets such that each digit occurs in each position exactly 40 times. That is, I want 400 triplets such that

np.sum(triplets[:,c]==d) == 40

is True for all c in [0,1,2] and all d in [0,1,2,3,4,5,6,7,8,9], and with triplets a 400 x 3 numpy array containing the subset.

I think that such subsets exist, but I am not sure, since I haven't buckled down to try to work out the math (I may not have the ability to do so even if I do buckle down, and I definitely don't have the time to do so, regardless). I can't figure out how to construct any such subsets from scratch (I wrote some aggressively mediocre code to do this that kind of works sometimes) or to select the right elements from the full set (assuming there are some).

I wrote some less mediocre code to sample randomly from the full subset and score each subset based on how much it deviates from the 40-of-each-digit criterion, and I found a subset with these tallies (rows are triplet position, columns are digits):

[[43, 41, 39, 40, 37, 40, 42, 42, 37, 39],
 [43, 41, 39, 38, 41, 39, 44, 38, 40, 37],
 [43, 38, 40, 38, 38, 41, 42, 44, 39, 37]]

Of course, randomly sampling from approximately 1.92e+213 total subsets of size 400 from the 720 total set of triplets isn't terribly efficient.

So, is there a solution to this problem? A commenter on reddit's intuition is that this problem is NP-complete, but I don't know enough about the relevant math or computer science to have particularly strong intuitions about this possibility. Should I just be happy with the best solution I stumbled on?

You could try using integer linear programming (ILP).  Use the following variables:

We have a variable $x_{ijk}$ for each triplet $ijk$, which is 1 if triplet $ijk$ is selected to be included in your set of 400, or 0 otherwise.
We have a variable $y_{ip}$ to count the number of times that digit $i$ appears in position $p$ among the selected triplets.

Now add constraints to capture all of your requirements:

We want to select 400 triplets: $\sum_{i,j,k} x_{ijk} = 400$.
We want each digit in each position to appear 40 times: $\sum_{i,p} y_{ip} = 40$.
We want the $x$'s and $y$'s to be consistent:

$$\begin{align}
  y_{i1} &= \sum_{j,k} x_{ijk}\\
  y_{j2} &= \sum_{i,k} x_{ijk}\\
  y_{k3} &= \sum_{i,j} x_{ijk}
  \end{align}$$

Finally, we require $0 \le x_{ijk} \le 1$ and $0 \le y_{ip} \le 1$ for all variables.

Now give the resulting system to an integer linear programming solver, and see if it can find a solution.

If it can't find a solution after a reasonable amount of time, your next step could be to find as small a subset as possible (not necessarily size 400, but hopefully not too much larger than 400).  Thus, replace $\sum_{i,p} y_{ip} = 40$ with $\sum_{i,p} y_{ip} \ge 40$, and instead of the constraint $\sum_{i,j,k} x_{ijk} = 400$, ask the ILP solver to minimize the objective function $\sum_{i,j,k} x_{ijk}$.  That will find a way to ensure each digit is presented at least as many times as desired, using as few trials as possible.


$O(n^2)$ and $O(n\log n)$ exercise There is an  exercise which says : Al and Bob are arguing about their algorithms. Al claims his $O(n \log n)$-time method is always faster than Bob’s $O(n^2)$-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $n<100$, the $O(n^2)$-time algorithm runs faster, and only when $n\ge 100$ is the $O(n \log n)$-time one better. Explain how this is possible.

Consider for Al $f_{Al} \in O(n \log n) $:
$$f_{Al}(n)=\begin{cases}n\log n, & \text{ when }n\lt 100 & \\
n  , &\text{ when }n \geqslant 100\end{cases}$$
For Bob let's take $f_{Bob}(n) \in O(n^2)$
$$f_{Bob}(n)=\begin{cases}n, & \text{ when }n\lt 100 & \\
n\log n  , &\text{ when }n \geqslant 100\end{cases}$$
Note also, that since for asymptotic relations it is only important what happens from some number to infinity, then Bob and Al are arguing in vain.


Types of Automated Theorem Provers I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

Which are the relevant automated theorem provers? I found A Review of Theorem Provers

Is this still current?

Which ones are still very active, i.e. which are currently used beyond the group that created it?

Find the series' next question here.

The categorization in that list is certainly still current.

Perhaps one new category has emerged, namely, dependently-typed programming languages. These are essentially automated theorem provers where the primary goal is not proving theorems, but programming. Due to the Curry-Howard correspondence, these two concepts are strongly intertwined. The ultimate goal of such programming languages is to write programs that have much stronger guarantees than regular typed programming languages. People also use these for theorem proving. Some new systems falling into this category include Agda and Epigram. One of the key characteristics of such languages is that they put a lot of effort into making it easier for programmers to define inductive families of datatypes. A simple example is a vector, which depends upon natural numbers (defined inductively).

Regarding which ones are still very active, I think they all are. Coq, Isabelle, Twelf, and PVS are used a lot in the programming languages community. Maude is used extensively in modelling systems. (Personally, I've used Coq and Maude.)

I'd never heard of a few of them. In the pdf you link to, there are links to the theorem provers. Some links are current, some are broken. Gandalf now seems to be some sort of bearded wizard.

The theorem provers mentioned in “A Review of Theorem Provers” are:

ALF: subsumbed by ALFA, Coq, and Agda.
ALFA: seems to no longer unsupported.
COQ: actively supported.
MetaPRL: seems to be no longer supported.
NuPRL: actively supported.
HOL: actively supported.
PVS: actively supported.
Isabelle: actively supported.
TWELF: actively supported.
ACL2: actively supported.
INKA: seems to be no longer supported.
GANDALF: seems to be no longer supported.
TPS: may still be active, but has only a small following.
OTTER: may no longer be supported.
SETHEO: replaced by E-SETHEO, which seems to no longer be supported.
SPASS: seems to be still active.
EQP: seems to be no longer supported.
MAUDE: very actively supported.
OMEGA: seems to be no longer supported.
Mizar: actively supported.

There are undoubtedly many new automated theorem provers that have not been mentioned in this list.

For completeness, as suggested by Raphael, there are site archiving proofs made using various tools. For example:

The Archive of Formal Proofs for Isabelle
Formalized Mathematics for Mizar
The Constructive Coq Repository
The ACL2 Books Directory
Selections from the PRL Math Library
NASA Langley PVS Libraries


Finding Language of a CFG Say you are given the following CFG $G$:
$$
S \to S_1 \mid S_2 \\
S_1 \to AbAS_1c \mid \epsilon \\
S_2 \to BaBS_2c \mid \epsilon \\
A \to Aa \mid \epsilon \\
B \to Bb \mid \epsilon
$$

What is $L(G)$?

So far I've derived the following regular expressions:

$ S \rightarrow (a^*ba^*)^*c \mid (b^*ab^*)^*c$

So far I've come up with this $L(G)$:

$L(G) = \{ (a^nba^n)^qc \mid (b^nab^n)^*q : n,q \geq 0    \}$

When you approach the second $S_1$ do you include the $c$ ( As in, finish $S_1c$ and the go recursive)?

Let's consider "half" of your problem: $S\to AbASc \mid \epsilon$, and $A\to aA \mid \epsilon$. It is important to realize that the number of $b$'s and $c$'s generated is equal. Try to express that in your solution.

At the same time, when two $A$'s are generated, they will generate an arbitrary number of $a$'s. One of your solutions claims these numbers are always the same, but they are not.

Personally I would prefer to write this language as $L(G_{\frac12}) = \{ wc^k \mid w\in\{a,b\}^*, k\ge1, \#_b(w) = k\} \cup \{\epsilon\}$, where $\#_b(w)$ is the notation for the number of occurrences of letter $b$ in the string $w$.
Alternatively, if you want to avoid that notation perhaps $L(G_{\frac12}) = \{ a^{n_0}ba^{n_1}b\dots ba^{n_k}c^k \mid k\ge1, n_0,\dots,n_k\ge 0\}\cup \{\epsilon\}$.

It is not immediate how to write this using "regular expressions" as the equality of the number of $b$'s and $c$'s is not regular property itself. Also we cannot put the star-operator inside set brackets, as the star yields a language itself, so it would be proper to write
$L(G_{\frac12}) = \bigcup_{k\ge1} (a^*b)^ka^*c^k \cup \{\epsilon\} = \bigcup_{k\ge0} (a^*ba^*)^kc^k $ .

Sorry about the $\dots \cup \{\epsilon\}$ in several of these solutions. Allowing $k=0$ would not give the right answer, as that would add $a^*$ to the language, which is not generated by the grammar.


Selection, crossover and mutation function choice in genetic algorithms I have been developing a GA for one of the projects I'm working on. I have everything implemented with no problems and I really like how GAs work in general, it's a really cool and relatively new concept. However I'm wondering which specific algorithms I should use for selection, crossover and mutation.

I understand that it often depends on what your data type is, for example individuals who's chromosome order is important should use crossover algorithms listed on this Wikipedia article (with maybe a few more to be added to that list), but how do I choose between them? What should I consider when I am selecting which algorithms to use for these three things?

Currently I have implemented Tournament selection, partially matched crossover and index shuffling for mutation and this gives me the exact output I want, but how do I know these are the best choice for my problem.

(P.S. This is purposefully as abstract as possible, I'm not looking for an answer to my specific problem but more how anybody can go about choosing which algorithms are best for their particular situation.)

SELECTION. Different types of selections will have different advantages and disadvantages. You will mostly find the right one through trial and error.

CROSSOVER. The optimal crossover technique is usually problem-specific. A general rule is to avoid using a single point crossover, as suggested by this paper.

MUTATION. Some mutation guidelines are provided in this paper.


How to use PHOG and LPQ features for Emotion Recognition? I have a database that consists of PHOG and LPQ features for each image. Now, I wish to train an SVM on these features for emotion recognition i.e SVM classifies the images on basis of emotion in the image.

Please provide a detailed procedure on how to use these features to train SVM.

To train your SVM inevitably you need some baseline, which can be accquired from FERA 2011 contest. The whole procedure using this data is described in Emotion Recognition Using PHOG and LPQ features by Abhinav Dhall, Akshay Asthana, Roland Goecke and Tom Gedeon. After reading that there is a follow up FERA 2015.


(reference) Where can I learn more about I/O operations in OS? I have basic understanding of file I/O. I know how to operate the read and write system calls in Linux. I know that there is blocking and non-blocking I/O. I want to know more about the underlying mechanism in OS for I/O. How is blocking and non-blocking I/O implemented? How do the kernel I/O buffers work? How big are they and when are they "erased"? For example if there is an open socket how much data will be kept in the kernel buffer before the data is overwritten?
I prefer a book of some kind. And please don't tell me to go and read the source. I konw that if I REALLY want to know how those things work that is the best I can do, but I simply am unable to dedicate so much time to this subject.

It is pretty complex because there are several layers between the actual hard-disk and the software implementation of sockets. In today's x86 computers, the actual hard-disk is read using the Intel's AHCI controller which is a PCI device. All SATA plugs on your motherboard are directly connected to the AHCI. The AHCI will control the hard-disk and present a complex interface to software so that it can read/write to/from the hard-disk.
The best way to learn those things is to write an OS yourself. Get the basics of bootloading then write a minimal OS and this knowledge will come by itself over time. The MCFG ACPI table informs software of the address of the beginning of the PCI configuration space. Then you can scan PCI buses (more often only bus 0 for home computers). On bus 0 you can have up to 32 devices which can each have up to 8 functions. The function is what the device actually does. Each function of each device will have a configuration space which allows to get more information on the function. It will present class IDs and subclass IDs will allow to identify the different devices. As stated on osdev.org (https://wiki.osdev.org/AHCI).

An AHCI controller can be found by enumerating the PCI bus. It has a class id 0x01 (mass storage device) and normally a subclass id 0x06 (serial ATA). The vendor id and device id should also be checked to ensure it’s really an AHCI controller.

Once you found an AHCI on the PCI bus, you can look at the specification of the AHCI for implementing a driver: https://www.intel.com/content/www/us/en/io/serial-ata/serial-ata-ahci-spec-rev1-3-1.html. This spec really covers what you need to implement an AHCI driver.
Blocking versus non-blocking I/O is a software construct. Blocking I/O waits for the data buffer to be filed while non-blocking I/O will return immediately if there are no data ready. Non-blocking I/O expects you to call the read again so that you can get a full buffer. It isn't this complex for hard-disks while for network it is very complex. Basically, the AHCI is a DMA device (since it is PCI compliant and PCI devices are DMA in nature since they have access to RAM bypassing the CPU). I never implemented a driver for it but the AHCI will be triggered by a command and, once the command is completed, will trigger an interrupt on a certain vector using the MSI-X capability of PCI devices. The MSI-X capability allows to specify a vector to trigger on command completion.
I think this answer is a good starting point for you on what to read and what to do. I doubt there will be a good book on this matter for you to read. You should implement an AHCI driver and socket layer above this driver to really understand how it works under the hood. The socket layer is a POSIX specification that you can find on internet.


Are you allowed to have empty states on Turing machine? So I'm doing some exercises with Turing machine and quite often it happens that a given set of states can be achieved if and only if some character was met. Therefore, we may have some states q3-q7 which the machine may be pointed to if and only if we spotted a and (because of the task spec, for example), we know that we may find only some chars (say b, d but not c, e) from the input language there so there's no need to have a separate state for every symbol. Can I then just program the states I'll actually use there and have some void states or do I have to put something there (like just reprinting the found character) anyway, even though I'm 100% sure the machine will never go to the state for some symbols?

The output and transition functions have to be defined for all state and character combinations. But if you say you can't get into the state, it means that if you do get there, the input was invalid. Therefore simply append a definition like "and all transitions not mentioned so far are to a rejecting state" (which is an endless loop if you are doing a stop/don't stop machine).


What would remain of Quantum Computing if quantum states were real numbers? This question is motivated by my attempt to understand quantum computing and the source of its computational power.

Quantum statest are described by complex numbers. That is, 1 qubit is described by 2 complex numbers, one for each state (actually 1 complex number, due to the constraint and the invariance).

Quantum phenomena are  explained by the fact that quantum states consists of probability amplitutes (complex numbers) rather than actual probabilities (real numbers).

My question is, what if we would consider an alternative "pseudo-quantum" system, the states of which, unlike classical physics, still consist of a distribution over classical states, only it is now real-valued rather than complex-valued. What would remain of quantum computing (or "pseudo-quantum computing")?

One thing that would remain is that the number of dimensions in the system would still exponentially increase w.r.t. the number of pqubits (pseudo-qbits), which as far as I understand is one source of the power of quantum computing. That is, it would allow correlations/entanglement, contrary to classical computing, but I am not sure if this actually matters for comoutational power.

The gate set Hadamard + Toffoli is universal for quantum computation [1] and only uses real number coefficients (some negative). So all quantum algorithms can be run without involving imaginary numbers.

That being said, you will pay some representation overhead if you stick with just H+Tof. For example, you need an extra ancilla qubit and essentially every encoded operation will act on this qubit. This creates a false dependency between most operations, preventing parallelism and locality.

[1]: https://arxiv.org/abs/quant-ph/0301040


How to reduce the cost of search based on previous BFS? I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles.

My goal is to output a map, based on given location on the grid, with the shortest path to all  the cells on the grid, some thing like this:

4 3 2 3
3 2 1 2
4 x x 3
5 6 5 4

  The starting position is at node with the weight of 1. X represent the
  obstacles.

I achieve this goal using Breadth-first-search. My question is how can I reduce the cost of the next search if:
Only my location on the grid is changed, and/or,
if only the location of the obstacles is changes and/or
if both my location and the location of the obstacles is changed.

As for now I perform full recalculation in all those cases.

You have two very different situations in the next search condition. If the graph is set up to represent a grid, then the obstacles are simply removed edges to the vertex where the obstacle is, by moving obstacles you have changed the graph, so any new problem is a search on a new graph and the old results are meaningless. For any two verticies, to see if the new obstacles block the old path is easy, however to see if replacing the edges from the old graph will shorten the path requires you to redo path finding. So in the case of the obstacles changing any algorithm would involve much more work then just redoing the BFS, which is quite simple. As for a changed user position you could sacrifice initial cost and search for all other searches upfront, depending on how many times you want to call the algorithm this may or may not pay off, this case is very situation dependent.


Interpretation of this regular expression: (1*0*)* Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )?

For example, 110011001100 is part of this language set, but 1100100010 isn't?

Or can the values of the two * change for every repetition of the ( )?

For any two words $w_1$ and $w_2$, the regular expression $\texttt{((}w_1\texttt{)*(}w_2\texttt{)*)*}$ is equivalent to $\texttt{(}w_1\texttt{|}w_2\texttt{)*}$. Hence, both your examples are elements of the language generated by $\texttt{(1*0*)*}$.

In this setting, it is impossible to specify $w_1$ and $w_2$ occur equally often with a regular expression (except for a finite number of possibilities). Otherwise, you would be able to generate a non-regular language, in this case $\{ 1^n 0^n \mid n \in \mathbb{N} \}^\ast$.


DFA or NFA Construction I have to draw a DFA or NFA for a language that has two symbols lets say {0,1}. The condition is "such that exactly one of the two symbols 0 or 1 appears at least three times." I understood this as if 0 appears three times or more than 1 can be there for 0,1 or 2 times and if 1 appears for 3 times or more DFA fails and goes to dead state. The same will happen for the case if 1 appears 3 times or more and if 0 can be there for 0,1 or 2 times and if 0 appears for 3 times or more DFA fails and goes to dead state. I have been trying to create a DFA for this but failing everytime on condition like "01010". I am not sure if it is possible to create a DFA or NFA for this. I guess this is solvable by PDA only.
Need help in making sure that I am thinking in right direction.

You only have a limited number of states to worry about:

Let note them $Q_{i,j}$ where $i \in \{0,1,2,3,4\}$ is the number of 0 and $j \in \{0,1,2,3,4\}$ is the number of 1; each up to a max of 4 $\implies$ only 25 states.

Then the transition is
$\delta(Q_{i,j}, 0) = Q_{i+1,j}$ if $i<4$
$\delta(Q_{4,j}, 0) = Q_{4,j}$
$\delta(Q_{i,j}, 1) =Q_{i,j+1}$ if $j<4$
$\delta(Q_{i,4}, 1) =Q_{i,4}$

Then the starting state is $Q_{0,0}$ and the accepting states are all $Q_{i,j}$ with $i=0 \oplus j = 1$ (where $\oplus$ is the xor operator).


What are cases where we cannot perform LR parsing without augmented grammar? Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing.
The reason frequently is

It is required in cases where start symbol comes on right hand of any production
It is required when start symbol's RHS have multiple production.

I figured that if in the parse table's action part of very first state of DFA, we provide "success" under entry of '$' we would not require augmented grammar. Is that correct or i am missing something?
Edit: Here is how i think we can declare a parse as success:
Consider S ->  .a
After we reduce 'a' instead of going to goto(S) from our current state a tTop of stack, we can simply lookahead '$' and output success

Once we have a parsing table, we can parse (or reject) any sentence without any reference to the grammar. So at that point, the fact that the grammar was or was not augmented is essentially moot. (It would be meaningful if there were a user semantic action attached to the augmented start symbol's sole production, but that seems impossible, since the augmented start symbol's production was added automatically, not by the user.)
And it is indeed the case that most parser generators do in fact optimise their parse table by making the shift of the end-of-input marker the accept action, rather than waiting for the augmented start symbol's production to be reduced. With that optimisation, the augmented start symbol is never used in a parser action, so the symbol itself need not exist. If the parser generator augmented the grammar, that augmentation has essentially been undone, except for one little mystery: what is this end-of-input symbol which can be shifted? It doesn't appear in any reducible right-hand side.
Anyway, the point is that it's not parsing which requires an augmented grammar; the augmented grammar is necessary to create the parsing table. The cases where it is necessary are essentially the cases in which there is some non-default reduction action associated with an end-of-input symbol lookahead. That reduction action could only have been correctly added to the parsing table through the analysis of a state which includes the augmented start symbol's production.
(Strictly speaking, as alluded to earlier, the end-of-input symbol can't really exist in the parsing table unless it is present in some right-hand-side in the grammar, and it isn't present until the grammar is augmented; the augmentation not only adds an additional non-terminal, it also adds the end-of-input symbol itself.)


Decidability Problem given a turing machine M over the input alphabet $\Sigma $ , any state q of M and a word w $\epsilon\Sigma $* , does the computation of M on w visit the state q ?

Is this problem decidable ?

Let P(M,q,w) = "the computation of M on w visit q"

If we suppose P décidable, then the problem P' defined as :

P'(M,w) = w \in L(M)

is decidable.

Proof :
This a decision procedure for P'. Let M be a machine and w a word.
For each accepting state q of M, we run P(M,q,w).  If the answer
 is "yes" for some q, we return "yes". Otherwise, we return "no".

Since it is well known that P' isn't decidable (Rice theorem), we conclude P isn't decidable.


Why do we need "potential” for amortized analysis? In the current version as of the Wikipedia article “Potential method”, the amortized cost of each operation is defined as the following
$$
T_{\mathrm{amortized}}(o) = T_{\mathrm{actual}}(o) + C \cdot (\Phi(S_{\mathrm{after}}) - \Phi(S_{\mathrm{before}})),
$$

and the total amortized cost is
$$ \begin{align*}
T_{\mathrm{amortized}}(O) &= \sum_i (T_{\mathrm{actual}}(o_i) + C \cdot (\Phi(S_{i+1}) - \Phi(S_{i}))) \\ &= T_{\mathrm{actual}}(O) + C \cdot (\Phi(S_{\mathrm{final}}) - \Phi(S_{\mathrm{initial}})).
\end{align*} $$

I understand the formulas and understand $T_{\mathrm{amortized}}$ is an upper bound on $T_{\mathrm{actual}}$ if the initial potential is zero. And I think I understand the basic examples like "binary counter", "two stack FIFO", etc. However, I am puzzled this:

  The actual cost is part of the formula.

I might be wrong but it looks like the actual cost is a known quantity. If we already know the actual cost, why do we need to add the "potential" to get an upper bound? It looks useless to me. Can anyone help give an example in which such "potential analysis" is useful?

As is unfortunately sometimes the case, Wikipedia is doing a terrible job of explaining what amortized analysis actually is.

The idea of amortized analysis is that while operations may have a bad worst case cost, their average cost could be much lower. Average cost means different things in different circumstances. In amortized analysis, here is what it means:

  Suppose that you have a data structure supporting operations $O_1,\ldots,O_r$. We say that these operations have amortized cost $c_1,\ldots,c_r$ if the cost of the sequence $O_{i_1},\ldots,O_{i_n}$ of operations is at most
  $$
c_{i_1} + \cdots + c_{i_n}.
$$

This definition is a bit simplistic, since sometimes the amortized cost depends on other auxiliary parameters such as the overall number of operations or the number of operations of a specific type.

The potential method is one way of carrying out amortized analysis, that is, of proving that the operations in a certain data structure have some amortized cost. Stated differently, if you want to prove that the amortized cost of $O_1,\ldots,O_r$ is $c_1,\ldots,c_r$, then one of the techniques is the potential method. There are other techniques as well.

How does the potential method work? You define a potential function $\Phi$ on the state of the data structure. The potential function must be always non-negative, and for the initial data structure it must be zero. You then prove that if at state $S_{\text{before}}$ you execute operation $O_i$ which leads to state $S_{\text{after}}$, then the cost $T_{\text{actual}}$ of the operation satisfies
$$
T_{\text{actual}} \leq c_i + \Phi(S_{\text{before}}) - \Phi(S_{\text{after}}).
$$
Given that this holds for all $i$, consider a sequence of operations $O_{i_1},\ldots,O_{i_n}$, and denote the corresponding states of the data structure by $S_0,\ldots,S_n$. The upper bound on $T_{\text{actual}}$ implies that the total cost of these operations is at most
$$
\begin{align*}
\sum_{t=1}^n [c_{i_t} + \Phi(S_{t-1}) - \Phi(S_t)] &= \sum_{t=1}^n c_{i_t} + \sum_{t=1}^n [\Phi(S_{t-1}) - \Phi(S_t)] \\ &=
\sum_{t=1}^n c_{i_t} + \Phi(S_0) - \Phi(S_n) \\ &=
\sum_{t=1}^n c_{i_t} - \Phi(S_n) \\ &\leq
\sum_{t=1}^n c_{i_t},
\end{align*}
$$
which was to be proven.


What are the k characters which make the most complete words? Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ characters to learn, where "best" is defined as the set of $k$ with which the most complete words can be spelled.  Ie, if I know these $k$ characters I can spell $N_k$ words.  What is the maximum $N_k$ for every $k$ and which characters should I choose?

Checking a given set of $k$ words is equivalent to a Scrabble problem, but searching the space becomes very hard very fast.  This problem is of limited interest in English where $M=26$ but is more important in Chinese or Japanese where $M \sim 10^3$.

I thought of considering the bipartite graph of characters and the words that they make but I'm not sure what the best search strategy is.  I'm somewhat pessimistic that this problem is strictly solvable and therefore I am willing to try heuristic or stochastic methods.

If you take each word as a set of characters, you're looking for sets of size k that contain the most words as subsets.  For a given word of j unique characters out of an alphabet of size N, you have (N-j) choose (k-j) possible supersets, ie all the sets of size k that have the original j characters plus any (k-j) others.

Some time ago I worked on an algorithm for a similar problem that might be modified for this case.  I'll try to sketch how it would work in this case.

Briefly, the solution is to walk all the "words" through their candidate supersets (a factorial number) in a fixed order, identify any runs of identical values that indicate a number of words that fit in the same superset, and to save the run that's longest.

This is essentially an n-way merge, looking for runs of identical values on the output.  I did this with a heap of iterators where I would pull the smallest value, count it, increment it (find the next superset in its range of possible supersets), and re-insert it into the heap.  This process provably visits every possible superset and counts the words that it covers.

What makes this possibly tractable is a pruning rule that skips candidates with sub-maximal runs.  What I realized while coding the above is that if my only interest is runs of length L or greater, then if I look L elements ahead I can see if the current run stops before L elements, and furthermore (with some careful reasoning) eliminate all intervening values from consideration and skip to whatever value is L elements ahead.

The problem I was solving originally was association-rule mining, which walks each set through its subsets rather than supersets, and this method worked well in that case.


Combining 2 problems in NP into one Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$.
Can S be solved with oracle access to only one problem in $NP$?

That is, can B and C somehow be combined into one problem in $NP$ (thus showing S is in $P^{NP}$)?

There are at least two ways to do it. The first is to take a disjoint sum of $B$ and $C$, which can be done in many ways, for example
$$
\{0x : x \in B\} \cup \{1y : y \in C\}.
$$
The second is to use an NP-complete language $L$ as an oracle. Since any problem in NP reduces to $L$ in polynomial time, you can simulate a $B$-oracle using an $L$-oracle.


What advantage do quadratic basis functions have over gaussian basis functions in RBF implementations? I've been reading up recently on radial basis functions, and I've recently moved from Gaussian basis functions of the form $\phi(x)=\exp(-\alpha||x-x_i||)$ to multiquadratic basis functions. My source is this paper, which is referenced in an algorithm that I'm looking at.

The basis function for the multiquadratic RBF is given as $\phi(x)=\sqrt{||x-x_i||^2+R^2}$, where $R$ is a shape parameter. While it's certainly possible to solve the set of linear equations in a basis function and get a valid result for any equation, this choice of basis functions seems odd. Compared to a Gaussian basis function, where the effect of a basis function with a large value of $||x-x_i||$ approaches zero, multiquadratics grow increasingly rapidly as the radius increases.

Intuitively, this seems like a strange choice for a basis function, since distant points in a training data set would seemingly influence the results of a local solution more than nearby points. Why is this function used as a basis function, and what advantages does it have over something like a Gaussian basis function?

...a strange choice for a basis function, since distant points in a training data set would seemingly influence the results of a local solution more than nearby points. Why is this function used as a basis function?

The sum of their influences quickly fades away. It's well illustrated in 1d, where we can represent a spline either piece-wise, locally controlled, or as one, 'global' RBF sum with $|x|$ kernel (see here for example). This might seem strange as each $c_i|x-x_i|$ term is unbounded. Yet, together they cancel out automagically at a distance. You can see it by following the derivation at the link. Another example is a system of electric charges overall neutral.

  what advantages does it have over something like a Gaussian basis function?

Multiquadric and other globally supported RBF have a good hole-filling property: if you have holes that are irregular with unknown scales, they're going to be smoothly interpolated over according to surrounding trends from neighborhoods of corresponding scales. If your dataset has a regular sparsity of one radius you can estimate, you can use instead compactly supported RBF, or Gaussian RBF which is practically local.


Simple example: 2-approximation for vertex cover I am having trouble finding an example for the following algorithm to prove that it calculates a 2-approximation:

  Repeatedly select a vertex $v$ of highest degree, add one of its edges $(v,w)$ to the cover, and remove all edges incident to $v$ or $w$.

Please give me insights on how to pick an example.

Hint:

Prove the stronger claim that if $M$ is any matching, then any vertex cover must contain at least $|M|$ vertices.
Conversely, if $M$ is any maximal matching (a matching which cannot be extended), then the $2|M|$ vertices in $M$ form a vertex cover.
Show that the greedy algorithm that you describe constructs a maximal matching.
Conclude that your algorithm (modified so that it outputs a set of vertices rather than a set of edges) is a 2-approximation for minimum vertex cover.
Consider the complete bipartite graph $K_{n,n}$. What is its minimum vertex cover? What vertex cover does your algorithm produce?


Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as "good" and practical as any other polynomial algorithm? If the complexity of an arbitrary algorithm to solve any NP problem after analysis is $\Theta(2^\sqrt{n})$ then is this algorithm considered as "good" and practical algorithm?

I know that in algorithm analysis and computational complexity theory every algorithm with any polynomial complexity is considered as "good" and practical algorithm, although in mathematics and calculus $2^\sqrt{n}$ isn't polynomial by definition, but so $n\log n$, but $\Theta(n\log n)$ counts as "good" and practical algorithm to solve any NP problem.

I have already graphed the functions: $x, x\log_2x, x^2, 2^\sqrt{x}$ and $x^3$ by using some online function plotter, and for some large $x$, it appears that $ x^3>2^\sqrt{x}>x^2>x\log_2x>x$

So I think that $\Theta(2^\sqrt{n})$ is practical and "good" as $\Theta(n\log n)$ is, although both of them are not polynomial by definition.

Am I right?

Complexity is how an algorithm increases its number of steps in comparison to $n$ when we scale $n$ to a large value.

For very small $n$ , an algorithm with complexity $\Theta(2^\sqrt{n})$ can behave nearly as good as an algorithm running in polynomial time.But if we increase the $n$ , then certainly the algorithm with polynomial time will give much faster results.That's how algorithms are compared.One important thing to remember is that your $n$ is a variable related to input size and if this occurs as a power of something in time complexity then you can be sure that the algorithm is going to take a lot of time for large values of $n$.

$\Theta(2^\sqrt{n})$ is not as good as $\Theta(n\log n)$


Doing induction on recurrences correctly I have $$T(n)=T(n-1)+n^{2}$$
And I know, by drawing the recursion tree that this is $\Theta (n^{3})$
However, if I try claiming that it's $O(n^{2})$ through induction:
$$T(n)\le c(n-1)^{2}+n^{2}\le cn^{2}$$
which evaluates to
$$c\ge \frac{n^2}{2n-1}$$
Which makes $c>0$ for all $n>1$ and concludes that the recurrence is $O(n^{2})$ which is not correct.
So what am I missing?

The error is that $c(n-1)^2 + n^2 = cn^2 - 2cn + c +n^2 \leq (c+1)n^2$, so the constant $c$ is in fact no constant, since it grows with every step.
So you get that when $n$ increases by 1, $c$ also does, so you have $O(n) \cdot n^2$, so $O(n^3)$.


What does normalizing with hidden bit really mean? I have  a question related to representing numbers in base 2 with floating point. For example, if I have such a number $$0.000011 \cdot 2^3$$ then is its normalized form this?
$$1.1\cdot 2^{-2}$$
Generally speaking about normalizing, normalizing with hidden bit, does it imply that the first number of mantissa should always be zero, or does hidden bit just mean that a "one" should be taken left to the point?

Generally speaking, normalized means "put in scientific notation."  That just means, the mantissa should never start with 0, and should be less than the base.  In binary that means the mantissa must be "1".  Since the mantissa of a normalized binary floating point number is always 1, we don't need to store the 1.  The first mantissa bit is hidden in the sense that it always exists, but we don't actually store the bit, because we know its value is 1.

So your normalized result ($1.1 \times 2^{-2}$) is correct, and it is correct because you've moved the first 1 to the left of the binary point.


Answering questions about the recurrence of certain aspects of an algorithm I am thoroughly confused by a problem that was brought up in class:

Given the following pseudocode for a function RANDOM which generates a random number based off of recursion:

function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/2, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/6
3.      if x = 0 then
3.1         return (RANDOM(n-1) + RANDOM(n-2))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n) + 2*RANDOM(n-1))
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n) + RANDOM(n) + 3)
5.2     end-if
6.  end-if
end-RANDOM

Answer the following three questions:

Give the recurrence equation for the expected running time of RANDOM.
Give the exact recurrence equation for the expected number of recursive calls expected by a call to RANDOM(n).
Give the exact recurrence equation for the expected number of times the return statement at line 5.1 is executed, in all calls to RANDOM(n), recursive or not.

Our professor gave us a version of this pseudocode that goes like this:

function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/3, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/3
3.      if x = 0 then
3.1         return (RANDOM(n))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n-1) + 1)
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n-1) + RANDOM(n-1) + 1)
5.2     end-if
6.  end-if
end-RANDOM

And answered the three questions as follows:

1)

T(n) = expected running time of RANDOM

$$
T(1) = 1
$$

$$
T(n) = 1 + \frac{T(n)}{3} + \frac{T(n-1)}{3} + \frac{T(n-1) + T(n-1)}{3}
$$

which, after some algebra, comes out to equal:

$$
T(1) = 1
$$

$$
T(n) =\frac 32 * T(n-1) + 1,
$$
, where $n>=1$.

I have one question about the answer to this problem. Why does the constant $1$ in the original equation not matter to the equation? Is it because it is being lumped in with constant time?

2)

R(n) = the expected number of recursive calls executed by a call to RANDOM(n). $$
R(1) = 0
$$

$$
R(n) = \frac{1+R(n)}{3} + \frac{1+R(n-1)}{3} + \frac{2+2*R(n-1)}{3}
$$

, which, after some algebra, comes out to:

$$
R(1) = 0
$$

$$
R(n) = \frac 32 * R(n-1) + 2
$$

, where $ n>0 $.

I have a couple of questions about the set-up of this problem.

Why is 1 added to the numerators of the first two rational numbers?
Similarly, why is 2 added to the numerator of the last rational number?

Finally,

3)

C(n) = the exact number of returns from line 5.1 of RANDOM(n), recursive or not.
$$
C(1) = 0
$$

$$
C(n) = \frac {C(n)}{3} + \frac {C(n-1)}{3} + \frac {1+2*C(n-1)}{3}
$$

, which, after some algebra, comes out to be:

$$
C(1) = 0
$$

$$
C(n) = \frac 32 * C(n-1) + \frac 12
$$

, where $n>0$.

My main question for this answer is: why is 1 added to the last rational number in the expression? What does that 1 represent?

I am so lost, and desperate. Any attempt to shine light on these answers would be such a great help to me. Thank you.

Firstly, there is one minor typo in the question. The "$T(n) =\frac 32 * T(n-1) + 1$" should be "$T(n) =\frac 32 * (T(n-1) + 1)$" since this equality is said to be obtained by simple algebra from the equality above it. However, this typo does not affect either the question or this answer.

The answer to all of your questions are so simple that I can hardly imagine that you missed it. Well, on the other hand, it is indeed very easy to miss it.

Let me give you a simple example to illustrate the answer. Suppose we have the following function, which computes the factorial.

function FACTORIAL(n)
    if n = 1 then
        return 1
    else
        return  n * FACTORIAL(n-1)
    end-if

Suppose we have made a call, FACTORIAL(4). That means we must have called FACTORIAL(3), FACTORIAL(2) and finally FACTORIAL(1). So we have made four calls to this function in total, the last three of which are called recursively. In fact, we have the following recurrence relations for $U(n)$, the number of recursive calls made in FACTORIAL(n).
$$U(1) = 0$$
$$U(n) = 1 + U(n-1), \text { for } n\gt 1$$
Notice the first "1" in the last equality, which stands for the call to FACTORIAL with parameter $n-1$ in the code, n * FACTORIAL(n-1) while $U(n-1)$ comes from the number of recursive calls made by FACTORIAL(n-1). In other words, the recursive calls made by FACTORIAL(n-1) does not include that call itself, which is, though of course, counted towards the recursive calls made by FACTORIAL(n). We can also check by contradiction. Let us suppose we did not have that "1". Then we would get $U(4)=U(3)=U(2)=U(1)=0$, which said that we had made no recursive calls to FACTORIAL when we had computed FACTORIAL(4), which is not true at all.

In the same way as in this simple example, all those constant 1's and one 2 in the question come from right where the calls are made. For example, when x = 2, the function will return (3*RANDOM(n-1) + RANDOM(n-1) + 1), which incurs $(1+R(n-1)) + (1+ R(n-1)) = 2 + 2*R(n-1)$ recursive calls.


Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP.
The equation has total n variables and each clause is a 2SAT equation in itself in a subset of variables from 1 to n.
Example:
F = [(x1 || x2 ) && ( !x2 || x3) && (x3 || x4)] || [(x2 || x5) && (x3 || x6) && (!x4 || !x6)] || ....
The equation F is a DNF of 2SAT equations, which has say m clauses. Is finding a solution to this in NP? If yes how?
Also, specifically I also want to know if finding False instances of equation F is in P or NP as well.

First, let me note that the question's title is a bit misleading, because $P$ is a subset of $NP$. See also Yuval Filmus's comment. I assume what you intended to ask is whether it's in $P$ or in $NP \setminus P$.
Also, the name "DNF" specifically refers to a disjunction of elementary conjunctions, not a disjunction of arbitrary functions. What you are describing is not a DNF, but a disjunction of CNFs.

With that out of the way, here's my answer.

To satisfy a disjunction of 2-CNFs, all you need is to satisfy one of them. So, if you apply the 2-SAT algorithm to the first of the CNFs and get a "yes", then the answer to the whole problem is "yes". Otherwise, you just move on to the second one, and so on. Shouldn't take long, since you only have m of them. If none of them can be satisfied individually, i.e. they are all constant zeroes, then obviously the entire thing is a constant zero.
So the answer to the first part is: the problem is in P, with the following decision algorithm:
For every 2-CNF, apply the "normal" 2-SAT algorithm (the resolution rule) to determine if it's satisfiable or not. If "yes", just return "yes". If you went through all of them without finding a "yes", then return "no".

Now, finding the "False" cases of that formula (also known as the problem of tautology) is another question entirely. For one thing, tautology for ORs of ANDs of ORs is equivalent to satisfiability for ANDs of ORs of ANDs, by De Morgan's rule. But that's just a more general case of an already general SAT problem, isn't it?
Consider what happens when you restrict the set of possible formulas to those in which every two-element disjunction is really just one element, repeated. So it is a formula like
$$
F = [(x_1 \vee x_1 ) \& ( \neg x_2 \vee \neg x_2) \& (x_3 \vee x_3)] \vee [(x_2 \vee x_2) \& (x_4 \vee x_4) \& (x_5 \vee x_5)] \vee ...
$$
which is equivalent to
$$
F = [x_1 \& \neg x_2 \& x_3] \vee [x_2 \& x_4 \& x_5] \vee ...
$$
which is just a normal DNF. After the De Morgan transformation, you get a normal CNF, whose satisfiability is known to be NP-hard. Therefore, any problem that includes this one as a subset will also be at least NP-hard.
Obviously, the problem in question won't be outside NP, because it is still polynomially verifiable. So the answer to your second question is "in NP, but not in P".


Can we apply binary search for finding key 'x' in unsorted array? Suppose we are given A, an array of size n, comprised of an increasing sequence of numbers followed immediately by a decreasing one. What is worst case time complexity of optimal algorithm to determine if a given number x is in the array?

The explanation given on the this site is confusing to me. How we can apply binary search on unsorted array?

They have provided following explanation => This is an application of Binary search, which has time complexity $Θ(log n)$ in worst case.

We can find the break point (where the type of sequence changes) in theta(log n). Then we can search individually on both sides of the break point (each of which is a sorted sequence). So overall theta(log n) only.


Automorphism of a Graph with a given Set of Permutations Given a graph $H$.  A set of permutations $\alpha$ which contains permutations of vertices of $H$.

The permutation set $\alpha$ has  automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the number of total subgraphs. These subgraphs are connected. These permutations can be extended to the automorphism of $H$. By extending, we mean that  automorphism of subgraphs can be extended to the automorphism of graph $H$. This concept is similar to E. Luks' paper of graph siomorphism of bounded valence.

Each subgraph has constant number of vertices. The adjacency matrix of $H$ is -

$$H = \begin{bmatrix}
H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\
R_{(x,x-1)^{T}} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\
R_{(x,1)^{T}} & R_{(x-1,1)^{T}} & R_{(x-2,1)^{T}} & \dots & \dots &H_{1} \end{bmatrix}$$

The adjacency matrix of graph $H_k \cup  H_e$ is $M_{(k,e)}$ where   $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right) $,  where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$.  Here, $R_{k,e}$ represents  edges  between $H_k,  H_e$.

Problem: How to find  an automorphism of $H$ in polynomial time (in $\alpha$)?

Note:

$\alpha$ is the generating set of autmorphsim group of  $H$.

If you only want an automorphism, then just consider the identity permutation.  That's an automorphism -- the trivial automorphism.

If you want a non-trivial automorphism, then if I understand your problem statement, this is as hard as the graph automorphism problem.  No polynomial-time algorithm is known for this problem.  It's not known to be NP-complete (it's not even known to be GI-complete).  Nonetheless, finding a polynomial-time algorithm for this problem is an open problem, so you shouldn't expect it to be easy to find a polynomial-time algorithm for your problem, either.

In practice you can use open-source tools like Nauty, BLISS, or SAUCY to find an automorphism; on most graphs they (empirically) are very fast.

Justification of claim that this is as hard as graph automorphism:

We can reduce graph automorphism to your problem.  Let $G$ be an arbitrary undirected graph, with $n$ vertices.  Construct an undirected graph $H$ with $2n$ vertices as follows: for each vertex $v$ of $G$, add another vertex $v'$, and add an edge $(v,v')$.  Keep all the edges between unprimed vertices, but don't add any edges between primed vertices.

Note that the automorphisms of $G$ are in one-to-one correspondence with the automorphisms of $H$.  If $\pi$ is an automorphism of $G$, it can be extended to an automorphism of $H$ simply by permuting the primed vertices in the same way as the unprimed vertices.  If $\pi'$ is an automorphism of $H$, by projecting it to the vertex set of $G$ we obtain an automorphism of $G$.

Now define $H_1,\dots,H_n$ as follows: each $H_i$ is the subgraph induced by the two vertices $v_i,v'_i$.  In other words, $H_i$ has vertex set $\{v_i,v'_i\}$ and has a single edge $(v_i,v'_i)$.  Thus, $H_i$ has a non-trivial automorphism that swaps $v_i$ and $v'_i$, and this corresponds to a permutation $\pi_i$ of $H$ (one that leaves all other vertices of $H$ fixed).  Define $\alpha$ to be this set of permutations.

Now if you can find a non-trivial automorphism of $H$, you can immediately obtain a non-trivial automorphism of $G$ (i.e., you've found a way to solve the graph automorphism problem on an arbitrary graph $G$).  If $H$ has no non-trivial automorphism, neither does $G$.  This completes the reduction.


Is $K(b|a) \geq 1$ if $a\neq b$? Since $K(a|a) = 0$, is $K(b|a) \geq 1$ when $a\neq b$, as we need at least one bit to distinguish between $K(a|a)$ and $K(b|a)$?  If not true in general, is it true if $a$ and $b$ are elegant programs?

Whether $K(a|a) = 0$ could depend on your universal computer. The only thing you can say in general is that $K(a|a) \leq C$ for some constant $C$ independent of $a$.

You can arrange for a universal computer for which $K(a|a) = 0$ for all $a$, and then indeed $K(b|a) > 0$ for all $b \neq a$, since there is only one program whose length is zero, and given $a$ it generates $a$.


Is there a single valid definition for a Turing Machine, or is it mutable? I'm just learning about Turing Machines, and I'm a bit confused by the difference in formal description between Wikipedia and my textbook.

My textbook says the following:

$$M=\langle Q,\Sigma,\Gamma,\delta,q_{0},q_{accept}, q_{reject} \rangle$$

where:

$Q$ is the set of states,
$\Sigma$ is the input alphabet not containing the blank symbol $\sqcup$,
$\Gamma$ is the tape alphabet, where $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$,
$\delta: Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$ is the transition function,
$q_0\in Q$ is the start state,
$q_{accept},q_{reject}\in Q$ are the accepting and rejecting states, respectively, and $q_{accept}\neq q_{reject}$

While Wikipedia states

  Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

  $Q$ is a finite, non-empty set of states
  $\Gamma$ is a finite, non-empty set of the tape alphabet/symbols
  $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols
  $q_0 \in Q$ is the initial state
  $F \subseteq Q$ is the set of final or accepting states.
  $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)

There are obviously a few similarities, but there are a few differences as well. Namely the ordering of the items in the 7-tuple $M$. Also, my textbook has three entries for separate special states, and the Wikipedia entry has only two - My book doesn't have a special element just for the blank character.

The ordering of the items in the 7-tuple M is completely immaterial to the behavior of the Turing machine. There is no "correct" or "incorrect" ordering; but I would say that both orderings are essentially the same definition. And I don't see that the blank character is treated any differently in the two definitions. In both, it's part of the tape alphabet but not the input alphabet.

For the two definitions to be effectively different, you would need to find a difference that does not correspond to a re-ordering of the 7-tuple, or is just in the wording of how the blank symbol is treated.

The only actual difference between the two definitions seems to be that your book has $q_{\mathrm{accept}}$ and $q_{\mathrm{reject}}$ as the halting states, while Wikipedia permits a general set $F$ of halting states. This is because your book only deals with Turing machines that compute languages (so for every string $x$, either $x \in L$ or $x \not\in L$) while Wikipedia also wants to handle Turing machines that compute functions. For a Turing machine that computes a function, you can assume that there is only one final state, $q_{\mathrm{halt}}$; the value of the function will be written on the tape when the Turing machine halts.


Ambiguity in choosing the best ER model I am actually little bit confused when I am reading through the text - Database system concepts by Henry F. Korth and others

I won't be able to understand one thing, which one of the following models I have to use when I have to design the ER diagram.

As the textbook says:

  We are going to treat the telephone as an entity when one may want to keep extra information about a telephone such as its location, or its type (like mobile, video phone or a plain telephone etc) or all who share the telephone. Thus, treating telephone as an entity is more general than treating it as an attribute

What I want to clarify is: If I draw the ER diagram by choosing telephone as a composite attribute having component attributes: telephone_number and location. Then I can also define the same way as an entity can do. Is it not correct to do it like this way?

If it is correct then what to use and when? If it is incorrect then why is it so.

one reason may be one person cannot have multiple phone numbers but we can design the same by making telephone as multi-valued attribute. So where I am going wrong?

If I draw the ER diagram by choosing telephone as a composite attribute having component attributes: telephone_number and location. In this case the DB Table for Employee will have 2 more columns telephone_number and telephone_location. This will lead to repetition which can lead to inconsistency.

Suppose, 2 different Employees (with id 1 and 2 respectively) share

telephone(111111, london) and
telephone(222222, paris)

Employee(id, name, street, city, telephone_number, telephone_location)

(1, xyz, abc, pqr, 111111, london)
(1, xyz, abc, pqr, 222222, paris)
(2, qwe, der, vfr, 111111, london)
(2, qwe, der, vfr, 222222, paris)

In above instance of table, not only the information is repeated but it creates a dependency telephone_number -> telephone_location which can lead to inconsistency , say if telephone_location of 111111 is changed from london to austria then, due to dependency you need to change telephone_location  value in (2, qwe, der, vfr, 111111, london) also. If forgotten then it will lead to inconsistency.

We are going to treat the telephone as an entity... In this case there will be a relationship entity which will translate to a independent DB Table (emp_telephone) having 2 columns Employee_id  and telephone_number. Therefore, the table instances will look like:

Employee(id, name, street, city)
(1, xyz, abc, pqr)
(2, qwe, der, vfr)

telephone(telephone_number, telephone_location)
(111111, london)
(222222, paris)

emp_telephone(Employee_id, telephone_number)
(1, 111111)
(1, 222222)
(2, 111111)
(2, 222222)

So, in above table instances no information is repeated and individual attribute/column value in table Employee and telephone can change independently yet linked via relationship emp_telephone.

Lastly, if telephone is kept as multi-valued attribute then it will lead to creation of a table similar to emp_telephone(Employee_id, telephone_number) in which each value of multi-valued attribute telephone along with primary-key of Employee will be kept.

That is:

Employee(id, name, street, city, telephone)
(1, xyz, abc, pqr, 111111/222222) //<-- note telephone is multi-valued
(2, qwe, der, vfr, 111111/222222) //<-- note telephone is multi-valued

will translate to

Employee(id, name, street, city)
(1, xyz, abc, pqr)
(2, qwe, der, vfr)

emp_telephone(Employee_id, telephone_number)
(1, 111111)
(1, 222222)
(2, 111111)
(2, 222222)

So, from above it seems that the conclusion is, if an entity has a composite attribute which can be shared then such attribute should be kept as separate entity.


Reduce the running by using doubly logarithmic tree I have two algorithms $A$ and $B$ to solve a problem $P$ of size $n$. Algorithm $A$ takes $O(\log n)$ time on the PRAM using $O(n \log n)$ operations (done in parallel). Algorithm $B$ reduces the size of $P$ by a constant factor in $O(\log n/ \log \log n)$ time using $O(n)$ operations (also done in parallel). Can I solve problem $P$ using $O(n)$ operations in $O(log n)$ time? I feel it can be done using a doubly logarithmic tree (not sure).

I will assume you are using parallel processing to achieve the advertised runtimes. Say algorithm B scales the size of P by a factor $c<1$. If we apply algorithm B $k$ times, the size of our problem will be $c^kn$. This will require time
$$\sum_{i=0}^{k-1}O(\log(c^in)/\log(\log(c^in)))=\sum_{i=0}^{k-1}O\left(\frac{i\log c+\log n}{\log(i\log c+\log n)}\right)$$
and
$$\sum_{i=0}^{k-1}O(c^in)=O\left(\frac{1-c^k}{1-c}n\right)$$
operations. Then an application of algorithm A will require $O(\log(c^kn))=O(k\log c+\log n)$ time with $O(c^kn\log(c^kn)=O(c^kn(k\log c+\log n))$ operations. For the overall operations to be $O(n)$, we need
$$\frac{1-c^k}{1-c}+c^k(k\log c+\log n)=O(1)$$
The only way for this to be constant with the $c^k\log n$ term is if $k$ depends on $n$. Then the $c^kk\log c$ term will shrink with $n$, since $\log c<0$. Taking $c^k=\frac{N}{\log n}$ for some positive constant $N$ gives
$$\frac{1}{1-c}-\frac{N}{(1-c)\log n}-\frac{N(\log \log n-\log N)}{\log n}+N=O(1)$$
As $n$ grows, we can see that this approaches $(1-c)^{-1}+N=O(1)$ from below. Plugging this into the expression for the runtime (sum of both parts) gives
$$O(\log n+\log N-\log \log n)+\sum_{i=0}^{k-1}O\left(\frac{i\log c+\log n}{\log(i\log c+\log n)}\right)$$
Since $\log c<0$, we can make the sum larger by doing $i\log c=k\log c$ on the bottom to get
$$O(\log n)+O\left(\frac{\frac{k(k-1)}{2}\log c+k\log n}{\log(k\log c+\log n)}\right)$$
Substituting the earlier expression for $k$ gives
$$O(\log n)+O\left(\frac{\substack{-\log (c) \log (N)+\log (c) \log (\log (n))+2 \log (N) \log (n)\\-2 \log (N) \log
(\log (n))+\log ^2(N)+\log ^2(\log (n))-2 \log (n) \log (\log (n))}}{2 \log (c)
\log (\log (N)+\log (n)-\log (\log (n)))}\right)$$
which simplifies to
$$O(\log n)+O\left(\frac{\log n \log \log n}{-\log (c)
\log (\log (N)+\log (n)-\log (\log (n)))}\right)$$
giving $O(\log n)$. That was tedious. Don't ask about the intermediate steps, I used the Wolfram Cloud.


Explaining why FFT is faster than DFT for the general public? How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?

FFT is an algorithm for computing the DFT. It is faster than the more obvious way of computing the DFT according to the formula.

Trying to explain DFT to the general public is already a stretch. Also, they probably don't know what an algorithm is. Perhaps you could say that there's a fast way of computing the DFT, and that's one more reason why it's so useful.


Problem: covering holes on a pipe The problem is informally defined as follows:

There is a pipe with holes in it, located at discrete positions. We have tubes that are used to cover the holes. Tubes come at fixed radius. Having a tube of a radius of 1, say, placed at position 3, covers holes at positions 2, 3, and 4. The puzzle is about providing positions for placing the tubes so that the lowest possible amount of tubes are used. Note that tubes are allowed to overlap each other.

For example, the tube radius is 1 and the holes are located at {2, 4, 6, 10}. Tubes need to be placed at position 3 (covering 2 and 4), 6 and 10.

Obviously this seems to be a covering problem, yet I wasn't able to find a specific, studied problem equivalent to this one. Any ideas on how to efficiently approach it?

EDIT: please consider an additional condition, which requires a tube's center to be placed exactly on top of a hole (for whatever strange reason). This should change the solution considerably.

If you see your position from left=0 to right=length(pipe), you can simply cover your holes from left to right.

When adding a new tube, put the leftmost remaining hole at the leftmost covered position by the tube. Then you cannot waste tube.

For instance with radius 2, a tube centered on pos k covers [k-2, k+2]. Then a tube with leftmost on k covers [k, k+4].

With holes at {2, 4, 5, 7, 9, 11}:
- first hole at 2 => first tube at [2, 6] centered on 4
- next hole at 7 => next tube at [7, 11] centered on 9


Solving $T(n)=4T(n/2)+n^2$ I am trying to solve a recurrence by using substitution method. The recurrence relation is:
$$T(n)=4T(n/2)+n^2$$
My guess is $T(n)$ is $\Theta(n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\le cn^2\log n$ but that did not work, I got $T(n)\le cn^2\log n+n^2$.

I then tried to show that, if $T(n)\le c_1 n^2\log n-c_2 n^2$, then it is also $\mathcal O(n^2\log n)$, but that also did not work and I got $T(n)\le c_1n^2\log(n/2)-c_2 n^2+n^2$.

What trick can I use to show that? Thanks.

You must subtract a lower order term in order to strengthen your inductive hypothesis: try

$T(n) \leq c_1 n^2 \lg n- c_2 n$ and you will be able to show by substitution that $T(n) = O(n^2 \lg n)$ for appropriate values of the constants ($c_2 > 1$ and $c_1$ big enough to correctly handle the initial conditions).


A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision tree for any comparison based sorting algorithms must have at least $n!$ leaves, and therefore at least one path of length $\left\lceil \log_{2}\left(n!\right)\right\rceil $, corresponding to the worst case performance of said algorithm.

Question: The condition $$\left\lceil \log_{2}\left(n!\right)\right\rceil \leq\#\text{ of comparisons in the worst case}$$

is a necessary  condition for any comparison based sorting algorithm. Is it also sufficient? e.g. if I am asked if it is possible to sort 5 elements in 7 comparisons, does it suffice to observe that $\log_{2}\left(5!\right)<7$ to deduce that such an algorithm must exist?

Following the conventions of Peczarski, Towards Optimal Sorting of 16 Elements, let us denote by $S(n)$ the optimal number of comparisons needed, and by $C(n)$ the information-theoretic lower bound $\lceil \log_2 n! \rceil$. It is known that $S(n) = C(n)$ for all $n \leq 11$, but $S(n) = C(n)+1$ for $12 \leq n \leq 15$. See Peczarski's paper for references. See also A036604.


If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable? Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

what about $\cup$ and $\times$ operators? If $A \cup B$ or $A \times B$ is recursively enumerable is it true to say both $A$ and $B$ are R.E.?

Notice that $\mathsf{RE}$ is not closed under complementation. Therefore there exists an $A\in\mathsf{RE}$ such that $B=A^c\notin\mathsf{RE}$, while $A\cap B$ and $A\cup B$ are trivially recursively enumerable.

However, when $A\times B\in\mathsf{RE}$, there is a Turing machine $\mathcal{M}$ accepts $(x,y)$ iff $x\in A$ and $y\in B$. Therefore $\mathcal{M}(x,y_0)$ for fixed $y_0\in B$ accepts the language $A$, and hence $A\in\mathsf{RE}$. For $B$ it is the same.

Update: I notice that I missed something in the case of $A\times B$. The conclusion holds only when both $A,B$ are not empty, since otherwise $A\times B=\varnothing\in\mathsf{RE}$ whatever the other one is.


Defining nullable symbols and the first set of a grammar I'm practicing for an upcoming exam and am being tripped up by a review problem. The problem gives the following grammar:

$$S \rightarrow AB\$$$
$$A \rightarrow \epsilon | a | (T)$$
$$T \rightarrow T, S | S$$
$$B \rightarrow b$$

As far as I can tell, the only nullable symbol is $A$. It is the only non-terminal whose production contains the null symbol $\epsilon$. I don't think $S$, which contains $A$ in it's production, is a nullable symbol since the same production also contains $B$, which is not a nullable symbol, and both $A$ and $B$ would need to be nullable for $S$ to also be nullable. Is $A$ really the only nullable symbol in this grammar, or am I misinformed?

As for the first set, frankly, I'm just having trouble following my professor's notes for creating the first set. Could anyone help here or point me to a good resource for this?

Thank you all so much.

A nonterminal $X$ is nullable if you can generate the empty word from it. For example, since $A \to \epsilon$, we see that $A$ is nullable, while since the only production involving $B$ is $B \to b$, we see that $B$ is not nullable.

In class, you were shown algorithms for determining which nonterminals are nullable. These algorithms are important for computers implementing parsers. Human beings can also use these algorithms to determine which nonterminals are nullable, but (i) outside of a classroom setting, humans never have the urge to determine which nonterminals are nullable, (ii) often it can be determined by "direct inspection".

The first set of a nonterminal consists of all initial terminals in words generated by $X$ (including $\epsilon$, if $X$ is nullable, at least in some definitions). For example, since the only word generated by $B$ is $b$, then $\mathrm{FIRST}(B) = \{ b \}$. Similarly, the productions of $A$ immediately imply that $\mathrm{FIRST}(A) = \{ \epsilon, a, (\}$. Continuing, since $S \to AB\$$ is the only production of $S$, then since $A$ is nullable and $B$ isn't, $\mathrm{FIRST}(S) = \{ a,(,b \}$. This is the same as $\mathrm{FIRST}(T)$. Here I am implementing the FIRST algorithm in my head, without ever looking at it. Algorithms are necessary for computers, not necessarily for humans.

Summarizing, I suggest focusing on the definitions of nullable and FIRST rather than on the algorithms that can be used to compute them. It is much more important to understand what you're doing (and why) then to memorize some algorithm which you will never ever use in the future.


Need Help Reducing Subset Sum to Show a Problem is NP-Complete I want to show that the following problem is NP-Complete:

For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such that $S$ has $k$ elements and all coordinates in the vector $\sum\limits_{x\in S} v_x$ are powers of two?

I'm quite certain that establishing a reduction from a known NP-Complete problem: the Knapsack Problem, Subset Sum or Vector Subset Sum (see section 4.3 here) to this problem is the correct way to approach this problem, but I'm having difficulty
figuring out how to exactly construct the reduction.

Concerning Subset Sum with a set $S$ and an integer $n$, I've tried taking one of the integer compositions of $n$, then splitting it up into its binary representation, and using that to dictate a desired vector. Then I would construct vectors $v_1,\ldots,v_n$ from the elements of $S$. But how do I create the input $k$?

One of the main issues here is that Subset Sum with a fixed subset size is not NP-complete. How do I work around that? Moreover, one of the trickier aspects of the problem is generalizing subset sum such that success is reported if some subset sums to any power of two. I don't see how not to appeal to multiple sub-instances of subset sum...

Is this the right approach? (If not, how should I do it?) What am I missing? How do I prove this?

Here are some hints:

Focus on the case $d = 1$.
Given a target $T$ in SUBSET-SUM, we can change it to a target $T'$ by adding the number $T' - T$; this should work if $T'$ is sufficiently large.
Given a SUBSET-SUM without constraints on the size of the subset, we can get an equivalent problem with such a constraint by adding a suitable number of zeroes to the (multi)set.

If we insist on a set, we need to do more cunning in 3.


Are there any non-finite automata? In automata theory, we all read automata as finite automata, from the very beginning. What I want to know is, why are automata finite? To be clear, what is it in an automaton that is finite - the alphabet, language, strings made with regular expressions, or what? And are there (in theory) any non-finite automata?

All automaton models you'll typically encounter are finitely represented; otherwise there would be uncountably many, which means they are not captured by Turing-complete models. Or, in CS-think, they'd be useless¹.

"Finite automata" are called finite because they only have a finite set of configurations (the input string aside). Pushdown automata, for instance, have a stack that can have arbitrary content -- there are infinitely many possible configurations.

Nota bene: Configurations of PDAs are still finitely represented! In fact, any computational model that falls inside Turing-computability has to have finitely representable configurations, otherwise TMs wouldn't be able to simulate them.

I consciously disregard hypercomputation here for the purpose of this question.


complexity theory NP Ok, I really need help because I have read in so many books but still don't understand the complexity class NP.

These are the books:

Theoretische Informatik; Katrin Erk, Lutz Priese (german)
Grundkurs: Theoretische Informatik; Gottfried Vossen, Kurt-Ulrich Witt (german)
Theoretische Informatik; Ingo Wegener (german)

Links:

https://de.wikipedia.org/wiki/NP_(Komplexitätsklasse) (german)
https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en (english)

And I actually have more links but I can't post them here because I don't have enough reputation

So far I know:

A problem L is in NP when there exists a nondeterministic algorithm which solves problem L in polynomial time.
NP includes decision problems. If there exists a solution for these problems, it should be possible to check with a deterministic algorithm in polynomial time whether the solution is indeed a solution.

To 1.: is the calculated solution an exact match or is it just an approximation? To 2.: is it just necessary to be able to check in polynomial time? For example: the solution is not indeed a solution but I was able to check it in polynomial time. Is the problem still in NP?

For a problem to be in NP, I must have a nondeterministic algorithm which solves the problem in polynomial time. The solution is an exact match and I must be able to check in polynomial time with an deterministic algorithm that the solution is indeed a solution????????????????

Can someone please help me to understand.

Further thoughts:
Let's take the TSP as an example.
Question: Does a tour exist <= k ?

Let's assume I wrote a nondeterministic algorithm, which calculates a tour <= k. So my answer would be: Yes, a tour like that exists.

However Vladimir wrote in his answer: If this question can be answered by a polynomial time nondeterministic algorithm, then the language L is in NP.

So I gave an answer 'yes'; that means the TSP is in NP?! However what about if my answer would be: No, a tour like that does not exist! ? Then the TSP would not be in NP?

And looking on the other definition: Further I answered: Yes, a tour like that exists, because my nondeterministic algorithm calculated a tour like that. Now if I can check with a deterministic algorithm in polynomial time that the calculated tour is indeed verified to be correct, then TSP is in NP !?

First of all note that a non-deterministic algorithm and a non-deterministic Turing machine are two different things.

A non-deterministic Turing machine is a computational model, while a non-deterministic algorithm "is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm" (Wikipedia). For example a QuickSort algorithm which partitions the array based on random choice of a pivot is a non-deterministic (probabilistic) algorithm.

So your definition 1 should be read as following

  A problem $L$ is in $NP$ when there exists a nondeterministic Turing machine which solves problem $L$ in polynomial time.

Similarly, the second definition should be read as following:

  NP includes decision problems. If there exists a solution for these problems, it should be possible to check on a deterministic Turing machine in polynomial time whether the solution is indeed a solution.

For the concept of $NP$ see this post.


Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart? Reference Question from Forouzon Book Computer Network.
Find the status of the following generator related to two isolated, single-bit errors.
$$x^{15} + x^{14} + 1$$
Answer given :
This polynomial cannot divide any error of type $x^t + 1$ if t is less than 32,768. This means
that a codeword with two isolated errors that are next to each other or up to 32,768 bits
apart can be detected by this generator.
Can some one please help me why is this true...? Or even how should I have an in general approach to analyze such questions...?
(Sorry if this is very silly, but I am unable to get a grasp of how the reason works...!)

Your polynomial is primitive, which means that the order of $x$ modulo your polynomial is exactly $2^{15}-1$. In particular, $x^a \not\equiv 1$ modulo your polynomial for all $1 \leq a \leq 2^{15}-2$, which means that your polynomial doesn't divide $x^a-1$ for this range of $a$.

(This also means that your polynomial should divide $x^{2^{15}-1}-1$, in contrast to what the question claims.)


What use are groups, monoids, and rings in database computations? Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird.

All I could find is:

  Implementations of Monoids for interesting approximation algorithms,
  such as Bloom filter, HyperLogLog and CountMinSketch. These allow you
  to think of these sophisticated operations like you might numbers, and
  add them up in hadoop or online to produce powerful statistics and
  analytics.

and in another part of the GitHub page:

  It was originally developed as part of Scalding's Matrix API, where
  Matrices had values which are elements of
  Monoids, Groups, or Rings. Subsequently, it was clear that the code had broader application
  within Scalding and on other projects within Twitter.

What could this broader application be? within Twitter and for general interest?

It seems like composition aggregations of databases have a monoid-like structure.

Same question on Quora: What is Twitter's interest in abstract algebra (with algebird)?

I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups.  These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say).

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity).

By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid).

By using Rings, we can do matrix multiplication over things other than numbers (which on occasion we have done).

The algebird project itself (as well as the issue history) pretty clearly explains what is going on here: we are building a lot of algorithms for aggregation of large data sets, and leveraging the structure of the operations gives us a win on the systems side (which is usually the pain point when trying to productionize algorithms on 1000s of nodes).

Solve the systems problems once for any Semigroup/Monoid/Group/Ring, and then you can plug in any algorithm without having to think about Memcache, Hadoop, Storm, etc...


About the Identity function in Agda I've defined the identity function in Agda as follows:

idd : (∀ {ℓ} {A: Set ℓ}) → A → A
idd a = a

I want to ask you if the following reasonings are correct:

The type of this function is A -> A.
idd is a polymorphic function, where (∀ {ℓ} {A: Set ℓ}) matches any type.
Because is a polymorphic function, I can say idd is of dependent type.

Your code does not work. I would suggest that you forget about the universe levels for the time being (the $\ell$ thing) and focus on simpler things first. Here is working code:

idd : (A : Set) → A → A
idd A a = a

The type of idd is (A : Set) → A → A. It is a dependent product, i.e., it could be written as $\prod_{A : \mathsf{Set}} A \to A$ in mathematical notation. If we have a type B then the type of id B is B → B.

You say:

  The type of this function is A -> A.

No. The type if idd is exactly what it says, namely (A : Set) → A → A.

  idd is a polymorphic function, where (∀ {ℓ} {A: Set ℓ}) matches any type.

Let us forget about ℓ. In this case the question is whether idd is a polymorphic function. The answer is "yes" because A matches any type.

  Because is a polymorphic function, I can say idd is of dependent type.

No. This is the wrong way to think. The function idd does not have a dependent type. It has the fixed type (A : Set) → A → A. However, this fixed type is a dependent product.


Are objects appropriate for modeling the real world? First of all, I know objects are not meant to model the real world, although they have been marketed as such and perhaps that was an intention at some point.
Here I say 'modeling the real world' in a general sense. That includes simulations, modeling of abstract (non-real) concepts and modeling of business support applications, although I'm not sure it is appropriate to develop all of them in a single general-purpose OO language.
Under the assumption that modeling the real world in software development is a desirable and advantageous trait (not considering inappropriate models), I'm inspecting the foundations of object-oriented programming and the Simula languages.
However I'm asking this question in the hope that someone can provide a quick spoiler.
I am under the impression that objects (i.e. endurants) may not be enough to model the real world since a) their classes are static across time, e.g. a Person is always a Person, not a Child who becomes an Adult and thus his/her responsibilities and actions change b) processes (i.e. perdurants) are not first-class citizens as objects are, and c) time also is not a first-class citizen.
Aren't requirements such as these necessary for a language to properly model the real world? Why haven't they been included in the concept?

Object-oriented programming languages are designed to support programming.  Whether they "properly" model the real world is beside the point and not the primary goal.  So, when you ask "why haven't [these requirements] been included?", it's likely because those weren't considered relevant or necessary to the goal of supporting programming.
It's like saying "A hammer is no good for driving in a screw; why haven't the requirements of driving screws been included in the design of a hammer?"  Well, that's not what hammers are designed for.
Of course you could invent your own language that follows different principles.  You'd presumably end up with something that looks different.  I'm not sure you'd ever finish such a project; I suspect there would always be some aspect of the real world that isn't incorporated in the language, and at some point you'd have to accept imperfect fidelity to the real world.  In any case, that would be a different project, with different design goals, so it's no surprise that it might lead to a different result.


Equivalence classes of regular languages One used equivalence relation in regular languages is that for a language $L$ over alphabet $\Sigma$, $(x\sim^Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \Leftrightarrow yw\in L)$.

That means, if two words $x,y$ are not in the same class, there exists $w\in \Sigma^*$ such that $xw\in L$ but $yw \notin L$.

It is implied by Myhill–Nerode theorem, that if we have infinitely many equivalence classes for a language $L$, that $L$ is not a regular language.

My question is this:
Is it correct to say that if we have an infinite amount of equivalence classes then there are infinitely many different $w\in \Sigma^*$ that "breaks" such equivalence relation between those classes? If so, how do we prove it? If not, is there a counter-example?

Let $L$ be a non-regular language, and suppose that there were only finitely many separating words, say $n$. Construct a graph in which vertices are equivalence classes and the edge $([x],[y])$ (where $x,y$ are the lexicographically first words in their equivalence classes, and $x<y$) is colored by the set of words separating $[x]$ from $[y]$, where for each word $w$ we additionally indicate whether $xw \in L$ ("$w<$") or $yw \in L$ ("$w>$").

Ramsey's theorem states that there exists an infinite monochromatic clique $A$ colored $\chi$. Let $[x],[y],[z] \in A$, where $x < y < z$. We consider two possibilities:

If $w< \in \chi$ then we get a contradiction since due to $(x,y)$ we should have $yw \notin L$, whereas due to $(y,z)$ we should have $yw \in L$.
If $w> \in \chi$ then we reach a similar contradiction: considering the same edges as before, we should have $yw \in L$ and $yw \notin L$.

The finitary version of Ramsey's theorem shows that for each $n$, there is $N$ such that every language with at least $N$ equivalence classes must have at least $n$ separating words.


If P = NP, how do I prove I can find the maximum clique in polynomial time? I want to prove that if P = NP, then there is a polynomial time algorithm for finding the largest clique in an undirected graph.

I understand how to use a verifier to find this but my issue is since P = NP it doesn't want me to use a verifier. I'm not sure how to approach this.

Assuming $P=NP$, then $CLIQUE \in P$, so you can test for a clique of size $k$ in polynomial time for all $k$. So you can just test for a clique of each size between $1$ and $n$ where $n$ is the number of nodes.

Now that you have the max clique size, you just need to find it. You can do that by removing an abitrary node, then re-running then seeing if there still exists a clique of max size. You will be left with the max size clique.


Can a Multi-Tape Turing Machine have an infinite number of tapes? So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes.

I'd assume not since this would give an infinite transition function?

You need a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

Notice that it especially the number of heads should be bounded. Sure, you can use a 2d TM, however, there is still only one head in this model. If you would allow an infinite number of heads, then the configuration of a TM would be infinite. This will cause a lot of problems and would give a quite different model of computation.


k-ordered array problem An array $A[1...n]$ is said to be k-ordered if
$$A[i - k] \leq A[i] \leq A[i + k]$$
for all $i$ such that $k < i \leq n - k$.
For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.
Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

I can understand how the example array is two ordered, but I am having trouble understanding what the questions 1 and 2 are trying to say.
Can someone please explain to me the meaning of the questions in simple terms?
Thanks!
P.S. First time questioner here. Sorry if I missed anything.

Take your example
$$ A = [1,4,2,6,3,7,5,8]. $$
An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together:
$$
1,4,2,6,3,7,5,8 \\
1,2,3,4,5,6,7,8
$$
You can see that matching digits are at distance at most 2.

An array is 2-ordered if its even elements are 1-ordered and its odd elements are 1-ordered. This could be helpful in question 1. A similar property is true for 3-ordered arrays. How do these two properties combine? I suggest you try writing out a few 2- and 3-ordered arrays to see what the possibilities are.


algorithm to delete nodes that completely removes connectivity This is a distributed systems problem, but perhaps the graph theory gurus can help me.

I need an algorithm that that tells me which nodes to remove from the graph to completely remove connectivity.

See example:

The most intelligently thing to do would be to remove the bcasts nodes:

Can you help me? One way to solve this would using a SAT or ILP solver, but I want to if there are any other algorithms for this kind of task.

Your problem is: given a graph, find a minimum-sized set of vertices whose removal disconnects the graph.

This is the "minimum vertex cut" problem.  There are standard algorithms for this, based on network flow and the max-flow-min-cut theorem.  You need to modify the graph slightly to make two copies of nodes, then apply network flow (network flow on the original graph finds a minimum edge cut; you want a minimum vertex cut).  See https://en.wikipedia.org/wiki/Vertex_separator, https://en.wikipedia.org/wiki/Cut_(graph_theory), https://cstheory.stackexchange.com/q/2877/5038.


Classify an algorithm to maximize number of tips used by liquid handlers concurrently I'm looking for suggestions on algorithms, data structures or at least problems (so that I look for solutions in that domain) to consider. I realize that exact solution probably doesn't exist. But the more similar problems/solutions I can find the more ideas they may inspire.
We need to transfer reactants from source vials to target vials where they'll be mixed with other reactants and be a part of chemical reactions.
Settings: a liquid handling robot has up to 8 tips which can aspirate (suck in) & dispense (spit out) liquid from/to multiple vials. They can do this either simultaneously or one-by-one.
Input: list of source vials, list of target vials, mapping between source and target vials as well as volume to be transferred.
Goal: minimize time to transfer. This usually means maximize the amount of time tips work simultaneously. To simplify the problem - lets optimize (meaning group them) only dispense operations.
Example
E.g. we aspirate from Source vials and dispense to Target vials. In this example we'll use 4 tips:

Aspirate all 4 Source vials, then dispense to A1, B1, C1, D1
Dispense E1 with 1st tip, then use 1st & 3d tips to dispense to F1, H1, then dispense to G1
Use 2nd & 3d tip to dispense to A2, B2 then to C2, D2
The rest will be filled by 1 tip at a time.

Here color represents which Target Vial should receive liquid from which Source Vial:

Additional conditions

Simultaneous aspiration/dispense is possible only when vials are located in the same column.
Tips can change the spacing between them. E.g. 1st & 3d tip can either dispense to E1 & H1 or F1 & H1 simultaneously.
Tips have max volume (1mL). If you need to dispense more - you'll have to return back and aspirate more.
Volume to be dispensed is different in different locations.
We could've aspirated with 2 tips from the same vial and then transfer the same substance with these 2+ tips. But for simplicity let's not consider this option.

If we focus solely on the dispensing operation, we can formulate this as a Set Cover Problem. Namely, we are given a set of tips that have already aspirated some source liquids and we are asked to minimze the number of dispense operations to fill up a given column of target vials. In this simplified set up, we aren't allowed to go back and aspirate new source liquids and we assume that the target volumes are less than the tip capacities.
To set this up as a Set Cover Problem, we treat each target vial as its own element in the universe. We associate with each configuration of the tips (e.g.: position and tip spacing) a set corresponding to the target vials that may be covered by this configuration, taking into account the aspirated fluids in each tip (i.e.: a target vial is "covered" by a tip configuration, if there is a tip that has aspirated the appropriate fluid and positioned over that vial).


How does $LL(n)$ languages compare with $LR(0)$, for $n>0$? In the context of languages (not grammars), I know following:

  $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$
  $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)$
  $LL(0)\subset LR(0)$
  $LL(n)\subset LR(1)$ for all $n$'s

How does $LL(n)$ languages compare with $LR(0)$, for $n>1$?

They are incomparable.

Every $LR(0)$ language has the prefix property (no sentence is a prefix of another sentence). But many $LL(k)$ languages don't have this property ($a^*$, for example).
The language $\{a^nb^mc\mid n\ge m\ge 0\}$ is $LR(0)$ but is not $LL(k)$ for any $k$.


Mapping many transition functions into two transition functions Continuing from this answer: https://cs.stackexchange.com/a/56072/43035

I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two transition functions $\delta_0',\delta_1'$. How will conflicts be handled?

For example: $\delta_1(q_1, a) = (q_2, b, R)\\ \delta_2(q_1, a) = (q_3, c, L)\\ \delta_3(q_1, a) = (q_4, d, R)$

How can you map $\delta_3$?

Suppose that you have three options $o_1,o_2,o_3$.

You first guess whether to apply $o_1$ or not; if not, you stay in place.

If you didn't apply $o_1$, you guess whether to apply $o_2$ or $o_3$.

Here is how to implement it using transitions, using your example:
$$
\begin{align*}
&\delta_1(q_1,a) = (q_2,b,R) \\
&\delta_2(q_1,a) = (q_s,a,R) \\
&\delta_1(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_2(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_1(q_t,a) = (q_3,c,L) \\
&\delta_2(q_t,a) = (q_4,d,R)
\end{align*}
$$
Here $q_s,q_t$ are new states, and $\sigma$ is any tape symbol.


Finding solution of given recursive equation? $T(n) = 1+ \sum_{j=0}^{n-1} T(j)$
I've proved $2^n$ be the solution of this equation using induction. But is there any other way to find the solution? I just proved not solved.

The trick in this case is to consider differences:
$$
T(n)-T(n-1) = \left(1 + \sum_{j=0}^{n-1} T(j)\right) - \left(1 + \sum_{j=0}^{n-2} T(j)\right) = T(n-1).
$$
Hence $T(n) = 2T(n-1)$, and so $T(n) = 2^n T(0)$.


How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible? I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'm afraid I simply don't know it.
I'm given an algorithm that starts with four numbers $a$, $b$, $c$ and $d$ which can be chosen freely.
After each iteration, the numbers are recalculated as shown in the following images. $a_{n+1}=|a_n-b_n|\ $, $b_{n+1}=|b_n-c_n|\ $, $c_{n+1}=|c_n-d_n|\ $, $d_{n+1}=|d_n-a_n|\ $ for all $n\gt0$.

After a certain amount of time, this algorithm always results in all four columns ending and remaining at 0. Or so it appears. You can quickly try it out by replicating it in Excel or any other spreadsheet program.
The goal is to choose the four starting numbers a, b, c and d in such a way, that the columns all jump to 0 after the 50th iteration or later.
I have difficulties understanding how one can outsmart this algorithm, i.e., to make this algorithm compute as many rounds as possible before reaching all 0's. I've tried a brute force method by simple giving a, b, c and d random numbers with maximum lengths of 30 digits. And then seeing how far I can get. I let my computer try that for eight hours last night and the best I came up with was 17 several times - so obviously pure random brute force will not work and I will need a more thoughtful approach.
I'd be glad about any ideas!

I am a bit cautious just in case you might be taking part of some kind of open competition or exam.

Before I could reasonably believe that you are raising this question in good faith, I will just say I can reach 51 iterations without going to all zeros using less than 18 digits for each number.

As an evidence that I do have an answer, here are the last 5 digits of my numbers. This will not help anybody to get a better answer, except when you are super good at math, in which situation you probably do not need this too tenuous a hint anyway. However, it can be used to prove beyond any doubt in the future that I did know an answer.
$$(***00000, ***22634, ***22881, ***60047)$$

Per request of the questioner, I will explain the simple "secret" of how to get an answer briefly. A full update may or may be followed later.

What you want is to let $a_1, b_1,c_1,d_1$ look like $a_0, b_0,c_0,d_0$ exactly. Since they look like exactly, the $a_2, b_2, c_2, d_2$ will look like $a_1, b_1, c_1, d_1$ exactly. You see you can actually go on forever. It will break down only when we cannot express the number accurately enough in its numerical representation, which is enforced since the geocacher owner does not accept values like $\sqrt 2$ (just for an example; there may or may not be a $\sqrt 2$ in my answer).

What does it mean by exactly alike? Well, for example, if the two circles of numbers are the same except by a factor and a rotation.


Are Elementary Cellular Automata structures considered to be fractals? I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata.

But, what about the other rules from Elementary CA? Are they also considered to be fractals?

Is there a definition relating Elementary Cellular Automata and fractals?

Cellular automata can generate fractal patterns (as in the case of Rule 90), but they don't always (e.g., Rule 0).

Willson was perhaps the first to demonstrate that CA can produce fractal patterns in the early 80's.

Shortly thereafter Wolfram characterized the fractal properties of a variety of 2-D CAs.

A few years later Culik and Dube went a bit further and proved that certain types of CA :

  ...will always produce a highly regular [fractal] behavior on an arbitrary finite configuration as the initial seed.

The take-home message is that some very simple CA rule sets generate complex behavior, but others don't do anything interesting at all.