texts: Algorithm to find number of covering sets

texts:
UPD: The following problem comes from error correction codes, to be precise -- either maximum-likelihood or belief-propagation decoding when the spectrum of special failing subsets is known (to some extent). Then the failure probability can be formulated as follows.

Let us say the universe set is $\mathcal U = \{1,2,\dotsc,N\}$ and we have $M$ subsets of it: $S_1, S_2, \dotsc, S_M$ ($S_i \subseteq \mathcal U$ for each $i$). Given $W$, find number of $W$-subsets of $\mathcal U$ that cover at least one of $S_1, S_2, \dotsc, S_M$. Mathematically speaking -- find cardinality of the following set:
$$
\{S \subseteq \mathcal U : |S|=W, \exists i \text{ s.t. } S_i \subseteq S\} \,.
$$

NB: union of the sets $S_1, S_2, \dotsc, S_M$ is not necessarily $\mathcal U$.

The algorithm does not need to be the most efficient, as I just need to find these numbers for my other problem. Hence, say, running time of 1 hour is acceptable. (Well, in the worst case, even 1 day might be okay if there is nothing better). The order of parameters I am interested in: $N \approx 200$, $M \leq 50$, $|S_i| \leq 8$, $W \leq 30$.

UPD: It seems that to find exact answer is very hard, therefore I am also interested in good bounds and/or approximations.

Example. $N=4, M=2, S_1=\{1,2\}, S_2=\{2,3\}$.

If $W=1$, the answer is 0: there are no 1-subsets that cover either $S_1$ or $S_2$.

If $W=2$, the answer is 2: $S_1$ and $S_2$ themselves.

If $W=3$, the answer is 3: $\{1,2,3\}$ (covers both $S_1$ and $S_2$), $\{1,2,4\}$ (covers $S_1$), $\{2,3,4\}$ (covers $S_2$).

If $W=4$, the answer is 1: $\mathcal U = \{1,2,3,4\}$ covers anything.

UPD: $M$ is now much smaller.


texts: Partition array into K subsets, each with balanced sum

texts:
Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that

$A'_{1} = \{a_{1}, ...,a_{x}\}$

$A'_{2} = \{a_{x+1},...,a_{y}\}$

$...$

$A'_{k} = \{a_{z+1},...,a_{n}\}$

where each subarray $A'_{1},A'_{2}, ...,A'_{k}$ has sum of its elements closest to $\sigma; \sigma = \frac{\sum_{i = 1}^{n} {a_{i}}}{k}$

Example:  $A = \{{5,6,1,3,4,10\}}, k = 3$

$\sigma = \frac{29}{3} = 9.\overline{66} \approx 10$

Best solution to split array is:

$A'_{1} = \{5,6\}$

$A'_{2} = \{1,3,4\}$

$A'_{3} = \{10\}$

with sums $11, 8, 10$

One way to measure "badness" of each solution, is to define function $h(A_{1},...,A_{k}) = \sum_{i = 1}^{k} {(s_{i} - \sigma)^2}$, where $s_{i}$ is sum of elements of subarray $A_{i}$

Can you point me towards the solution? I've been trying for a few days now, and I'm no closer to an algorithm than I was few days ago.


texts:
suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t

each number should be in one pair and also every number should be paired
a pair(like 0-1) should be present in only one of the pairing. and also every possible pair should be present somewhere

i)   0-1   , 2-3  ,4-5

ii)  0-4   , 1-2  ,3-5

iii) 0-3   , 1-4  ,2-5

iv)  0-2   , 1-5  ,3-4

v)   0-5   , 1-3  ,2-4

similarly if I have N numbers. I need $(N-1)$ pairing of numbers s.t  in each pairing there are $N/2$ pairs.

essentially this is grouping $\binom{n}{2}$ combinations into  $n-1$ groups s.t each number is present exactly once in each group


texts: How to determine the carry vector of an integer addition

texts:
An integer addition can be represented as following:

$A + B = A \oplus B \oplus carry_{vector}$

My question is how to determine the carry vector from $A$ and $B$ (not from the result)?


texts:
In Haskell, are datatypes converted to the "Church encoding" i.e. folding the data type.  For example, given

data N = Z | S N

in Haskell, it can be converted to its church encoding by

foldN Z z s = z
foldN (S n) z s = s (foldN z s n)

Where if we do foldN m, we get the church encoding:

\z s . s (  .... s n ... )

In Proofs and Types, Girard shows how this works for any inductive datatype.  There are two questions I have: (1) is this actually how Haskell treats datatypes and (2) what is the equivalent construction for coinductive datatypes.


texts: (Percision & recall) Vs (Accuracy)? which one do I have to consider?

texts:
I am running several machine learning classifiers to predict something from my data. If I visualized the precision and recall tables as a result, is it enough to get clear idea about the proposed mdel? or do I have to consider the accuracy table in order to cover the issue?

I am running 3 different classifiers (svm, perceptron, and isolation forest) to detect anomalies in post arrays according to 3 groups of features sets extracted from the texts, so far I have the results for each classifier according to 1 and 2 features sets and 1 and 3 and for all together.

What I want to know is which classifier perform better(classify the text arrays to compromised or not ) with those combined extracted features, so far, I recognized that specific classifier with specific combined features has the highest precision value, but do I have to visualize the result of the recall and accuracy? Am I missing somehting?
What precisely do you mean by "perform better"? Better in what sense?

perform better means which classifier has the highest accuracy in classifying the text arrays to compromised text or not.


texts: Using machine learning to detect trend reversal in a time series

texts:
I'm starting to learn machine learning, and have honed in on a problem to get my hands dirty with: how to detect a trend reversal in a time series.

I've asked this question on stats.SE more than a year ago, but now I'm looking for a machine learning approach. How would I go about this specific problem vs. generally identifying patterns in time-series data?


texts: How China's Weibo deleted text from my video?

texts:
I made a home 45 min video of myself giving a presentation on a physics topic using my iphone 6. The format is quicktime .MOV - about 2.8 GB. I converted it to .mp4,down to 650MB,using a software avidemux.

After that I used a linux utility ffmpeg and used a 'drawtext' feature to add relevant  text/equations at relevant portions of my video. This is a .mpeg-4 to .mpeg-4  with little change in size  I understand it may be similar to a hard-sub with re-endcoding (I don't understand what is re-encoding). I uploaded it to youtube and China's youku and everything was working find.

I then made a post in China's Weibo (an equivalent to Twitter) with a link to my youku video. I got a surprise! The video plays perfectly, but somehow all the text that I added with 'drawtext' disappeared. I don't understand.

I know that Weibo is heavily censored, but I can't understand if somehow they would go to this extend. They might as well take away my audio track or delete my video link.

I ask a relative of mine who has a B.Sc in computer science and he told me there are ways using AI neural network to remove texts from my video. The text from my video is very clear with blue and a ttf font style.

Can someone confirm this is what Weibo did to my video, censoring all the texts. If true, how could I redo my video so that no one could remove the texts. I have the original .MOV files


texts: Genetic algorithm with a visited path list

texts:
I am currently working through the Computational Intelligence: An Introductionbook by Andries Engelbrecht.
I forked a simple implementation of a genetic algorithm trying to solve a path planning problem from path a to b.
I have previously completed the graph search chapters in Russel and Norvig's AIMA book.
I was curious to know if their have been any graph search variants for a genetic algorithm that like DFS or BFS keeps track of paths visited and then influences the fitness function or the generation of a new population.
From a novice's point of view it seems that the GA wastes search time by visiting states repeatedly.
Is anyone familiar with such a variant?
I have been unable to find anything available on the web.


texts: Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?


texts: How do you prove that two languages are equivalent?

texts:
How can you show that the Language accepted by an NFA and the reverse NFA is the same?

For a language $L$, there is an $L^R=\{ w^R \mid w \in L\}$

Let's say that $w^R$ is the string obtained by reversing the string $w$.

I know that it involves using induction on the length of the input, but I would really appreciate some help.


texts:
When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may not be uniformly random then; a famous example is RANDU.

The natural follow-up question is: what do you do? I can imagine several strategies.

Choose a PRNG that you know works well for $k$-tuples and sample $(\leq k)$-tuples by using subsequent numbers as components.

I assume that $k \leq 5$ is probably covered, but are there any for arbitrary $k$?
Use $k$ different PRNGs (different algorithms and/or different seeds) and
draw the $i$th component from the $i$th one.

I seem to remember that mixing PRNGs is not a good idea.
If the domain of your PRNG is big enough, use bits $i,k+i,2k+i, \dots$ for the $i$th component.

Seems sound and is probably the method of choice assumign real $U(0,1)$-numbers, but does not scale given finite resolution/domains in practice.
Use a bijection from the domain of your PRNG to the $k$-dimensional space you want to sample from, e.g. a generalized version of Cantor's pairing function.

The sizes of the resp. domains can become a problem here a well.

None of the approaches seems entirely reasonable. So what is the state of the art? What advice would you give a person who needs to sample uniformly random tuples?


texts: For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?

texts:
In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply connected region with these rectangle shapes is NP-complete. However the number of rectangle shapes $10^6$ seems pretty extreme. Maybe it's hard to close the gap on P vs. NP-complete for tiling in terms of the number of rectangle shapes available, but what if we allow more complex pieces such as non-rectangular Tetris pieces and larger non-rectangular pieces? (We could insist the piece shapes are all simply connected, but I'm not adamant about that).

Can we show NP-completeness for tiling a simply connected region with a much smaller set of (potentially non-rectangular) pieces available, compared to $10^6$?

The authors mention and rely upon an NP-completeness result for tiling with "Generalized Wang Tiles" that seem to use coloring as well as shape, and claim that NP-completeness can be achieved with a fixed set of 23 generalized Wang tiles. However I wasn't able to decipher this result to figure out how many ordinary non-colored (and e.g., perhaps also simply connected) tile shapes are needed to establish NP-completeness.


texts: Check a variable within a range with a binary variable

texts:
I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 or not.

Thanks


texts: What is the time complexity of sorting n words length wise and then alphabetically? Should we consider the length of the strings in the complexity?

texts:
Let's assume I have a list of some words found in the English dictionary:
["hat", "assume", "prepare", "cat", "ball", "brave", "help" .... ]
I want to sort these words (which are n in number) in a way, such that they are ordered based on their length, but if 2 words have the same length, they are ordered alphabetically.
What is the time complexity of this sorting operation?
Would it be fair to say that the complexity is just O(nlogn) and not take into consideration the length of the strings? If the largest length is S, can the complexity also involve a factor of S?


texts: Finding whether the language is CFL or regular

texts:
$L = (0^i 1)^n$ where  i=1,2,3,4...n  and n>=0

For eg :- 00010001 doesn't belong to the language as n=2 but i=3 at the beginning.

001001001 belongs to L as n=3 and i=2 in all cases.

I know the above language is not regular for sure as value of 'i' depends on value of 'n' and it requires comparison. So DFA not possible.

Now I am not sure to which class of language does the above language belong because to check number of zeroes or 'i', we need value of 'n' which can be found out only after reading the entire string.

Can someone please help?


texts: Algorithm for generating coprime number sequences?

texts:
Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother?

Ideally I'm looking for something that has random access abilities so i could ask for the 100th item in the set without having to first calculate items 0 to 99.

Also, I would like to be able to specify a minimum value for these numbers, to specify that none of them should less than 50 for example.

Does anyone know of an algorithm to do this, or at least satisfy part of my asks?

Thanks!


texts: Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time?

texts:
Let G(V,E) be the graph and V = {$V_1$,$V_2$,....,$V_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time.

We can have a matrix :
dp[s][i][j] : which computes for any subset (say s) of V whether there exists a hamiltonian path starting from vertex $V_i$ and ends at vertex $V_j$ if s includes $V_i$ and $V_j$.

Can we have only dp[s][i] and say whether there exists a hamiltonian path ending at vertex $V_i$ there by solving it in $O(2^n n^2)$ time. Can it be improved furthur?


texts:
Every time I ask why most people think that P ≠ NP, I get a response like "because theorem proving is harder than proof checking".

From this, I understand that proving theorems is hard. But why is this? In fact, it is known that a theorem, in mathematics, is a statement that has been proved on the basis of previously established statements. So a not proven theorem would not be called a theorem, would it? I mean, a theorem is easy to prove because it is defined to be so and people call it theorem because they know how to prove it, no? If we were talking about conjectures, I would have not asked this question.

When I was looking, I found this paper: Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. But this seems to confuse me furthermore.

I am sure I am missing something (maybe some obvious one). Would you please clarify this?


texts: Minimal length of a string that contains two strings

texts:
We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal.  Is there an efficient algorithm for this problem?

For example, if $a=1011$ and $b=0100$, the minimal string that include both: $c=101100$.  As you can see string $c$ includes both $a$ and $b$ (with the characters of $a$ appearing in the same order in $c$, possibly with other characters interspersed, and the same for $b$).

I think it can be solved by a dynamic programming algorithm.


texts: How to use c-gap problems to prove inapproximability?

texts:
Suppose there is a specific set function with some properties -  $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized. My goal is to show that designing a constant factor approximation algorithm in polynomial time is NP-Hard.

Correct me if I am wrong: As per these notes on gap reductions, we can design a c-gap problem with $OPT$ being the maximum value of $f$. The problem takes as input $\beta$. The goal is to answer YES if $OPT\geq \beta$. NO if $OPT< c\cdot \beta$. (here $c<1$).

To show the desired inapproximability, it would suffice to show the above c-gap problem is NP-Hard. My question is: Why is it this decision problem is designed for one $\beta$ when the optimimum value for the maximization problem is not known? Is the idea that, suppose you have a solver for the c-gap problem, you can call it with multiple values of $\beta$? If so, how many calls are possible?

Also any additional references on proving inapproximability would be greatly appreciated.


texts: Complexity class for concurrent algorithms

texts:
We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in  a similar way?

Motivation:

A sequential algorithm may be O(n7) but its parallel implementation might make it O(1) so what is the motivation and tradeoff between spending time to design lower complexity algorithms then simply paralyzing it to achieve an even better performance? How this fact could be incorporated in the complexity theory notations?

Note:

Writing a parallel version is also a challenge but many times its a low hanging fruit which can be quickly solved without much creativity.


texts: Proof for "It is my contention that these operations include all those which are used in the computation of a number"

texts:
In his famous paper, Turing briefly describes his machine and then states (p. 232) (emphasis mine):

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

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

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


texts: is there a way ensure that there only is flow through vertices c and d and not e or through d and e and not c. But not both at the same time. With an simple extension it is possible to put also minimum constraints on the network but this does not seem to help us.


texts: If graph isomorphism yields a polynomial time algorihtm

texts:
Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes.

If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible implication it has or what can we possibly deduce?

Thanks for any explanation


texts: What is the simplest known NP-Complete problem for testing P=NP solutions?

texts:
About a year and a half ago I asked this question regarding $\mathsf{P}=\mathsf{NP}$.  The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic.

With that stated, it is my understanding that $\mathsf{NP}$-complete problems are such that if a solution for $\mathsf{P}=\mathsf{NP}$ were found for that specific problem, then all $\mathsf{NP}$ problems could be solved using the same rules for resolving $\mathsf{NP}$.

With that stated, what is the simplest $\mathsf{P}=\mathsf{NP}$ problem outlined to date that is $\mathsf{NP}$-complete?

In other words, what is the most basic of problems that one could test a theoretical $\mathsf{P}=\mathsf{NP}$ solution against?  I'm aware of many of the examples such as the Traveling Salesman or Knapsack problems but I assume there could be even simpler scenarios where all properties of the $\mathsf{P}=\mathsf{NP}$ or $\mathsf{P}\ne\mathsf{NP}$ dilemma are present.


texts: Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular

texts:
Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that
$$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$
is a regular language.

I tried to build a NFA based on the DFA that accepts $L$ but failed to do so. I don't know how to ensure the $\, ww \,$ part. Please advise.


texts: Algorithm for travelling to top right corner in a room with random walls inside

texts:
A robot, let's say, Steve, is in the bottom left corner of a rectangular room, the size of which is unknown. His goal is to travel to the top left corner of the room and stop there. There are random walls present in the room. There always is a way to the corner.

Steve can do the following:

Move forward.
Turn left, right and around.
Detect if a wall is in front of him or not.
Detect if he is facing to the left, right, up or down.
Put/pick up a diamond in/from the slot he is standing in.
Detect if there is a diamond where he is standing.
Steve has an infinite numbers of diamonds.
Steve cannot count (that is, he functions as a finite state machine).

What I've thought of so far is using the right-handed method using which Steve will always arrive at the top right corner, but detecting it is the major problem, as there can be other places in the room with walls to the right and top. Consider this case, for example:

"S" represents Steve. His destination is (10, 8), but as we can see, there are 7 other places in the room which can be mistaken for the destination by simply checking for the bordering walls.


texts: Dictionary matching problem: dictionary size estimation

texts:
Suppose we solve dictionary matching problem for $d$ patterns with the Aho-Corasick algorithm. Then our main data structure consists of a trie with $n$ vertices and auxiliary structures. I want to estimate the dictionary size $d$ via $n$. It seems reasonable that $d = o(n)$, but maybe there is some research, that provides more accurate estimation of dictionary size based on real data.

So, what estimation for $d$ via trie size $n$ fit reality the best?


texts: Is it possible that the halting problem is solvable for all input except the machine's code?

texts:
This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help.

Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself? Basically:

Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

This seemingly resolves the contradiction. When we call the paradoxical Halts'(Halts'), we can't expect consistent behavior, but all other calls to Halts (and Halts') are legitimate and solvable.

I understand that this is highly unintuitive. If some pattern in the bits could reveal the behavior of all possible programs, why would it suddenly fall apart when the TM and input match? But can we mathematically eliminate this as a possibility?

And this reduced halting problem would not be uninteresting at all. Even if there were some meaningful program that took its own code as input it could trivially be rewritten to work on slightly different input. Of course this suggestion makes it even less understandable why a halting solution could exist with this one caveat but again, can we really mathematically eliminate this possibility?

Thanks for any help.


texts: Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]

texts:
What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements?

For the following 3-element list [1, 1, 2] I would expect the following result:

[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

So far I have the following result:

[1, 1, 2] <- duplicate
[1, 2, 1] <- duplicate
[1, 1, 2]
[1, 2, 1]
[2, 1, 1] <- duplicate
[2, 1, 1]

with algorithm below:

FUNCTION permute(array, nestingLevel) :
    FOR index = nestingLevel TO array size -1
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        SWAP array[nestingLevel] WITH array[index]
    END FOR

    IF recursionNestingLevel EQUAL TO array size - 1
        PRINT array
    END IF
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)


texts: What are the differences between approximation of AIXI and deep reinforcement learning

texts:
AIXI is a theoretical formulation for artificial general intelligence. While AIXI is computationally intractable, there are approximations of AIXI like https://arxiv.org/abs/0909.0801 that are computable.

Some time ago, I stumbled upon theoretical artificial general intelligence, and I would like to know what are the practical differences between approximations of AIXI and deep reinforcement learning methods.


texts: Review of Formal Verification and How to Apply it to Greenfield Project

texts:
Last year I looked heavily into Formal Verification, such as automated theorem proving, model checking, type systems, symbolic evaluation, and many others. I probably spent a few weeks or maybe months looking into it. At the time, I felt like I had a decent grasp of how it could be applied, yet still couldn't put my finger on exactly what first steps would be. Today, I have forgotten a significant portion of this stuff, or more specifically of implementation details. I get all the different branches of Formal Verification at a high theoretical classroom level, but I don't get how to apply it to writing real software.

The question here is how I can apply formal verification to a project if it were greenfield and free of constraints (yet at the same time, realistic meaning the problems can be solved within a reasonable amount of time). I'm wondering if one could explain relatively briefly how you would apply any/all Formal Verification techniques to gain that mathematical guarantee that your program matches a specification. How do the hardware people do it? How should it be done in software? Basically...

More specifically, nothing comes to mind other than writing unit/integration tests when it comes to making sure I'm building a super complicated program correctly (like an HTTP server). How could I apply model checking, or typechecking, or other things, to my advantage in terms of proofs / guarantees of program correctness (with regards to the specification)?


texts: Extremal graph. $2n$ vertices in which every subgraph of $n$ vertices has $k$ edges. Lower bound on the number of edges

texts:
Assume that a simple graph has $2n$ vertices and the property that every subset of $n$ vertices induces a subgraph with at least $k$ edges.
Question: What lower bounds are known on the total number of edges?

For example, if $k=n$, then the graph should have at least $5n$ edges.
We can see this by splitting the set of vertices into two disjoint sets $V_1,V_2$ such that $V_2$ induces a subgraph with minimum number of edges. Denote by $d_2(v)$ the number of edges of $v$ connecting it to a vertex of $V_2$.
If $v_1\in V_1$ and $v_2\in V_2$ we have that $d_2(v_1)\geq d_2(v_2)$, otherwise we can make $v_1,v_2$ switch subsets and make $V_2$ have less edges.
Assume that there is $v_1\in V_1$ with $d_2(v_1)\leq 2$. Then all $v_2\in V_2$ will have $d_2(v_2)\leq 2$. This gives at most $n$ edges in the graph induced by $V_2$ with equality only if $d_2(v_2)=2$ for all $v_2\in V_2$. Therefore, if $d_2(v_1)\leq2$ we must have $d_2(v_1)=2$ and $d_2(v_2)=2$ for all $v_2\in V_2$. But then switching $v_1$ and one of its $V_2$ adjacent vertices we degrease the number of edges in the graph induced by $V_2$.
Therefore, $d_2(v_1)\geq 3$ for all $v_1\in V_1$. This implies that we must have $n$ edges in the graph induced by $V_1$, also $n$ edges in the graph induced by $V_2$ and at least $3n$ edges going from vertices in $V_1$ to vertices in $V_2$. In total $5n$ edges.


texts: Prerequisites for studying parametrized complexity

texts: Which areas of CS/Math should one have mastered before diving into parametrized complexity?


texts: Given a tree find path that maximizes the median of the costs of edges

texts:
We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path is defined as a median of all costs of edges that lie on the path.

Let's define two types of costs of path between two nodes $i$ and $j$.

Cost 1: The number of edges on the path between $i$ and $j$.

Cost 2: We create array of all costs on edges on path between $i$ and $j$, then the cost is the median of this array. (In case of even number of elements we consider the median to be the bigger of the two middle elements).

Note that we don't need to know the starting and ending nodes in the best path, just its median.

For example:

N = 6, L = 3, R = 4
1 2 1
2 3 1
3 4 1
4 5 2
5 6 2
The best possible path is 2 -> 3 -> 4 -> 5 -> 6.
It is valid in terms of cost 1, the number of edges is 4, which is between L and R.
And in terms of cost 2 the costs of edges are {1, 1, 2, 2}, and the median in this array is 2, which is maximum possible.
Another valid path is 2 -> 3 -> 4 -> 5, but the median of costs of edges is 1, which is not maximum possible.

I have a solution in $O(N^2 \log N)$ that tries every possible path and saves the costs of edges in binary search tree, but is is possible to get faster solution?


texts: I want to verify some properties on finite traces. These properties can be in pLTLf (past LTLf) or LTLf. I want to be able to always traverse the trace forwards, which, depending on the algorithm, is only possible with the property being specified in exactly one of the two logics. Is there an algorithm that transforms a pLTLf formula into LTLf and vice versa?


texts: Does "$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$" hold given that $\sigma(F)\equiv F$ for a CNF formula $F$ built on a set $L$ of literals?

texts:
Suppose we have a CNF formula $F$ built on the set of literals $L=\{x_1,\neg x_1,\cdots,x_n,\neg x_n\}$ where each variable is used in at least one clause of $F$. Consider a permutation $\sigma$ of $L$ such that $\sigma(F)$ is logically equivalent to $F$ i.e. $\sigma(F)\equiv F$.

Does it hold that $\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$ ?

I tried to find a counter example without success.


texts: Runtime of algorithm to transpose a graph

texts: I am working with an algorithm to compute the transpose of a directed graph. Here is a rough overview of the algorithm: For each vertex in the graph, traverse each edge and add an edge from the neighbor to the parent node. The adding of an edge takes constant time, $O(1)$. And I figured, if I am traversing each edge, then the asymptotic run time should be $O(|E|)$. However, the run time of this algorithm is $O(|V| + |E|)$. The only way I can make sense of this is: once it reaches the final level of the tree (the roots), even though the nodes don't have any edges, the for loop will still iterate through those nodes. However, if I am taking this into account, then shouldn't it be $O(|V|)$. Why are we taking both $|V|$ and $|E|$ into account? Can someone can offer some insight to this?


texts: Check if a NFA accepts a string of non-prime length

texts:
Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.

My obvious [edit: wrong] answer is that, if $A$ has $n$ states, then I can simply check if it accepts any word of composite length $\le n$. This violently works, since the input alphabet is defined as finite.
Is there a more refined solution? And would that entail some involved graph search?
P.S. To give some context, this comes from an exercise that previously asked to find algorithms that solved the emptiness problem for regular languages, and the problem of equivalence between two NFAs. I solved those in an analogously simple fashion.


texts: SAT solvers for use in $P^{NP}$ and $NP^{NP}$

texts:
The original question I am answering:

Can you use SAT solvers to solve problems complete in $\Sigma_2^P,\Pi_2^P,\Delta_2^P$?

My first thought:

Venn Diagrams show that the PH encloses NP, but does not equal NP. Therefore, there should be some problems that cannot be solvable using SAT?

My second thought:

To be able to use a SAT solver on one of those PH classes, it would imply that they are reducible to SAT, and so $\Sigma_2^P = \Pi_2^P = \Delta_2^P = \mathsf{NP}$.

This would imply that PH collapses to NP, which we know not to be true.
Are these thoughts correct?


texts: Reservoir sampling algorithm probability

texts:
I'm reading about the reservoir sampling technique called Algorithm R.

The idea is we can take a sample of size $n$ from a population of size $N$ even when $N$ is unknown/too expensive to retrieve in $N$ time. I quote a sample implementation from wikipedia:

(*
 S has items to sample, R will contain the result
*)
ReservoirSample(S[1..n], R[1..k])
 // fill the reservoir array
 for i = 1 to k
     R[i] := S[i]

 // replace elements with gradually decreasing probability
 for i = k+1 to n
   j := random(1, i)   // important: inclusive range
   if j <= k
       R[j] := S[i]

The explanation for why this works:

  The algorithm creates a "reservoir" array of size $k$ and populates it with the first $k$ items of $S$.

That is pretty clear, the first for loop in the code sample does that. Then:

  It then iterates through the remaining elements of $S$ until $S$ is exhausted. At the $i$-th element of $S$, the algorithm generates a random number $j$ between $1$ and $i$. If $j$ is less than or equal to $k$, the $j$-th element of the reservoir array is replaced with the $i$-th element of $S$.

Also clear. But here comes the Math:

  In effect, for all $i$, the $i$-th element of $S$ is chosen to be included in the reservoir with probability $\frac{k}{i}$.

Hmm, I'm probably not well versed enougn in probablility theory, so can someone explain in more detail how the probability is $\frac{k}{i}$?

What I also don't get: do all elements have the same chance of being included in the (final) reservoir? From my understanding, it seems like the probability decreases for the elements at the end of $S$ to be included, then the reservoir will be skewed towards including the earlier elements, or am I misled?


texts: Generating all strings that a regular expressions describe

texts:
I'm having trouble generating the set of strings, which a regular expressions describe.
A typical regular expression can look like this:

[atom_0] atom_1 (atom_2 | atorm_3 | ... | atom_n-1) <var> [atom_n]

Or any other combination of the following:

[], means, that the atom inside of it can be omitted
(), one of the atoms (seperated by | (stands for OR)) inside the braces can be chosen
<>, variable.
atom, it can be thought as a constant, which is hard coded.

For example:

The [yellow] (dog | cat) named <animalName>

This expression describes the following set of strings:

The yellow dog named <animalName>;
The yellow cat named <animalName>;
The dog named <animalName>;
The cat named <animal Name>;

The strings can vary, depending on the variable <animalName>, but say, we have two names for <variableName> : Petsy and Rony, then w'll have:

The yellow dog named Petsy;
The yellow cat named Petsy;
The dog named Petsy;
The cat named Petsy;
The yellow dog named Rony;
The yellow cat named Rony;
The dog named Rony;
The cat named Rony;

Right now, I'm thinking that I could build a tree (or graph) from the expression and then a DFS or BFS can do the job.

Any comments or document/article references would be helpful to me.


texts: Can all deterministic non-oblivious Turing machines be simulated by oblivious ones?

texts:
According to Relations Among Complexity Measures by Pippenger & Fischer, the definition of an oblivious machine is:

An oblivious machine is one whose head movements are fixed functions of time, independent of the inputs to the machine.

In other words, a Turing machine $M$ is oblivious if and only if it exists a function $f: \mathbb{N} \rightarrow \mathbb{Z}^{k}$ and the location of each $M$'s heads can be determined by $f(n)$ with $n$ the number of steps run by the machine $M$ and $k$ the number of tapes.
In the abstract of the paper mentioned above, it is said:

Any machine with one-dimensional tapes can be simulated on-line by an oblivious machine with two one-dimensional tapes.

Now, let's imagine a non-oblivious Turing machine $M_{no}$ that can either accepts or rejects any input $x$. For instance:

if $x=00$, $M_{no}$ accepts the input after 10 steps;
if $x=01$, $M_{no}$ rejects the input after 12 steps;
if $x=10$, $M_{no}$ accepts the input after 8 steps;
if $x=11$, $M_{no}$ rejects the input after 7 steps.

According to Pippenger & Fischer, there is an oblivious Turing machine $M_o$ that can simulates $M_{no}$. As $M_{no}$ always halt, I could imagine an oblivious Turing machine that simulates it following the algorithm described by Pippenger & Fischer and halting after $n_{worst}$ steps which is the worst number of steps for any input of size $n$. In the example I gave, it is 12 for an input of size 2.
First question: is it possible to determine $n_{worst}$ in advance for every Turing machine?
But, what about another non-oblivious Turing machine $M_{inifnite\_no}$ which behaves exactly as $M_{no}$ except it never halts when the input is $x = 11$? In this case, $2_{worst}=+\infty$ and the oblivious machine simulating $M_{inifnite\_no}$ would never halts for any input of size 2 which is not the behavior of $M_{inifnite\_no}$. Therefore, this machine doesn't exist.
Second question: Is the theorem of Pippenger & Fischer only true for Turing machine that can halt?


texts:
I have a problem where I'm asked to prove that if P is a pushdown automaton, then  there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language as P.
I've tried to codify the stack alphabet of P in binary, using the same ammount of symbols for each representation so I know where the codification of one symbol starts and ends, but I don't know how to simulate P with P'.


texts: Design finite automata for this language

texts:
L = { w : w ∈ {a, b}* ∧ (u, v, z ∈ {a, b}*) (|u| = 2 ∧ |z| = 2 ∧ w =
  uvz ∧ u ≠ z)}

Can someone explain me this language? What is w = uvz supposed to mean?

I thought I understood correctly, so the words from this language could be for example: ε, aaab, aaba, bbaa, bbba...


texts: What is the relationship between "model of computation" and "algorithm"?

texts:
Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the other websites I've seen seem to agree). To me, this seems really close to the informal notion of algorithm, which is "a step by step description on how to calculate something". Furthermore, a function is called calculable if we can give an algorithm for it.

What is the relationship between this two concepts? For what I've seen, computational models such as Turing Machines or Lambda calculus are just formalisms to write algorithms within a particular syntax and semantics. For instance, a Turing machine specifies how to describe steps (n-uples) and gives a semantic of how this algorithm is interpreted. Similarly the lambda calculus specifies the syntax and the interpretation of calculus.

So, are models of computation syntactic/semantic rules for the formalization of algorithms? Why/why not? At this point, what's the difference between model of computation and programming language? Thank you for your replies.


texts: Can inherited attibutes be evaluated in bottom up parsing?

texts:
I have come across the following question in an exam:

  Can inherited attributes be evaluated in bottom-up parsing?

My approach went like this:

  Inherited attributes can never be evaluated in bottom-up parsing because the parent node is not constructed during parse yet when we visit the child node. In order to evaluate an inherited attribute of child node  we may need the value of parent nodes attributes hence we cannot get the parent nodes attributes as its not yet created hence we can not evaluate the child nodes inherited attributes.

Is my approach wrong? Am I conceptually missing anything?


texts: Proof for Transitivity of Weak Bisimulation ≈

texts:
I have already posted this question on the other page, but I was suggested to post it here as it might be more relevant.

I am currently following a course in concurrency theory and I am currently trying to prove that the Weak Bisimulation relation ≈ is an equivalence relation.

I have managed to prove cases for reflexivity and symmetry, however I can't seem to make the connection for transitivity. Does any one have any clues how can I go about this ?

I have tried the relation {(P,R) | ∃Q.P≈Q,and Q≈R} as my witness relation and then at one point I get stuck.

I assumed that P->a P' which gives me that there is Q =>a Q' and that P' ≈ Q' Now the thing is that since Q =>a Q' then by the definition of => Q ->tau* Q1 ->a Q2 ->tau* Q' Q1 ->a Q2 will cause some R1=>a R2 such that Q2 ≈ R2 Then I am not sure how to proceed to show that somehow there is a transition R =>a R' such that (P', R') are in R. May be I believe I have to use numerical induction on the number of tau ?

Thanks !


texts: NP hardness of partitioning a graph into two subgraphs

texts:
Given a planner graph which it's vertexes have weights and an integer, W, this graph should be partitioned into two subgraphs which sum of weights for each subgraph becomes at least W.

I wanted to show this is np hard by reduction and I have used Max cut to show that (in max cut we have a graph with weights for edges and need to partition it's vertexes into two subgraph which the sum of weights of edges between these two subgraph, becomes at least K)

I'm not sure about how to change weights of edges in max cut to weights of vertexes in the new problem, I've considered for each vertex weight the max weight of edges which it is an endpoint for, and W=K, is this correct?? if not how to consider the weights for vertexes and W?? or another problem should be used?? I appreciate if anybody guides me by the reduction.

ps: please consider that we can not use partition since it says at least W not W, or subset sum.


texts: Algorithms that must compute a global property?

texts: Could you give me examples of polynomial-time algorithms that must compute a global property over their entire input? A purely illustrative example of this might be a graph algorithm that somehow must count the total number of nodes before computing its final answer.


texts: Simplifying the boolean expression xy + (!x)z + yz with boolean algebra?

texts:
So using K-maps I was able to simplify xy + (!x)z + yz to xy + (!x)z, and I double-checked that the truth tables are the same.
I'm having trouble understanding how I would have used boolean algebra to get this result. I tried my usual tricks of adding zero, letting addition distribute over multiplication, etc., without avail.
Any thoughts appreciated.
Thanks.


texts: Insertion sort with pairs of numbers already in order

texts:
I am currently attempting to work out the number of comparisons that is done by insertion sort when the elements are already in sorted pairs, for example

$$4,5,22,23,1,2,19,20, \dots$$

Currently working to solve for the worst and average case number of comparisons done when a sentinel is used.

For worst case where each pair is out of order, what I've worked out is that the pattern for comparison goes $1 + 3 + 3 + 5 + 5 ... + n + n$, leading to a summation

$$\sum_{n=2}^{n/2}(2n-1)(2)$$

and I solved it to $(n^2+4/2) - 3 - (n-2)$.

Does this look about right? I'm now having trouble attempting to solve for the average case. Any idea how to go about this? Thanks for any help


texts: Construct neighbourhood relation graph for n sequences

texts:
Given $n$ sequences with length $m$, $s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$, where $c^i_j\in D$ is a partial ordered set and the partial order relation $\sqsubseteq$ on $D$ answers any query $x\sqsubseteq y$ in constant time.

We define the neighbourhood relation over $\{s_i\}$ as:

For any $\pi=\langle c_i \rangle \in \{s_i\},\tau=\langle c'_i \rangle \in \{s_i\}$, $\pi$ and $\tau$ are neighbours if and only if: (1) $\exists j$, $\neg(c_j\sqsubseteq c'_j)\lor\neg(c'_j\sqsubseteq c_j)$, and (2) $\forall i\neq j, c_i\sqsubseteq c'_i$ or $c'_i\sqsubseteq c_i$. The neighborhood relation is denoted as $\pi \sim \tau$.

An example is taking $=$ as $\sqsubseteq$, then $\pi\sim \tau$ means $\pi$ and $\tau$ have exactly one different item.

Another example is taking a flatten join-semilattice as $D$, then $\pi\sim\tau$ means $\pi$ and $\tau$ has at least one different item and all different item pairs of $\pi$ and $\tau$ contains at least one $\top$ except for one pair.

Now consider the undirected graph $G=(V, E)$, where $v_i \in V$ represent $s_i$, and $(v_i, v_j)\in E$ if and only if $s_i\sim s_j$.

Since for any two sequence $s_i, s_j$, $s_i\sim s_j$ needs $O(m)$ query of $\sqsubseteq$ and $\sqsubseteq$ takes constant time, the complexity of judging $s_i,s_j$ is $O(m)$, and there are $O(n^2)$ pair of $s_i,s_j$, the total complexity  is $O(mn^2)$.

Is there an algorithm for computing $G$ with better time complexity?

My initial effort is to consider given three sequence $s_i,s_j,s_k$, there seems does not exist an algorithm taking less than $3\times 2m$ query of $\sqsubseteq$, so the total complexity cannot be less than $O(mn^2)$, but I cannot prove it.


texts: Sorted unsigned integer intervals tree structure

texts:
The goal is to store sorted unsigned integer intervals that can overlap only in the boundaries, e.g., |0–10|10–50|100–110|110–200|. This structure will be created by some insert operations (the order matters) in the start and than queried by a lot of queries. The query is specified by interval and the result is all intervals from structure that has at least a partial overlap.

There is no need to delete inserted data (delete operation), but the new inserted interval can overwrite the existing ones. Please consider the following example.

|0–10|10–50|100–110|110–200|
insert: 40–70
|0–10|10–40|40–70|100–110|110–200|
insert: 105–115
|0–10|10–40|40–70|100–105|105–115|115–200|

What structure do you recommend?


texts: Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

texts:
Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.

More precisely, given a triplet $(i,j,k)$ with $i<j<k,$ it satisfies the question above if $A[i] \times A[j] \times A[k] = target$ and either ($j = i+1$ and $k > j+1$) or ($k = j+1$ and $i < j -1$.)

For example, if the list given is $A = [1,2,2,2,4]$ and target $= 8,$ then the answer is $2$ as $(0, 1, 4)$ and $(0, 3, 4)$ are the only triplets satisfying conditions above if we use $0$-based numbering.

I stucked at this question for 3 hours and not able to solve it.

Any hint is appreciated.


texts: Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?

texts:
Recall the standard argument for showing an AVL free is of size $\log n$:

  Let $n_h = $ be the minimum number of nodes of an AVL tree of height
  $h$. Then we have:

  $$ n_{h} \geq 1 + n_{h-1} + n_{h-2} \implies n_h > 2n_{h-2}$$ $$ n_h > 2^{\frac{h}{2} } \implies h < 2 \log n_h $$

  so the height of the tree is $O( \log n)$.

I understand the recurrence but I just don't understand why we argue about:

  be the minimum number of nodes of an AVL tree of height $h$

maybe my intuition is wrong but I thought that we'd want to argue about as many nodes as we can fit in a tree of height $h$ and show that it still balanced and show its $\log n$. Why is that reasoning incorrect?


texts: Q-learned policy differs from double-Q-learned policy

texts:
I implemented Q-learning and double-Q-learning as presented in Sutton's "Reinforcement Learning: An Introduction".
I test the algorithms on the OpenAI cliff walking gym and analyze the resulting policies after 500 episodes.

I was expecting the two policies to be the same, but actually the policies differ:

Policy learned with Q-learning:
(x represent the steps taken by a greedy policy evaluation, T is target, C is cliff)
o  o  o  o  o  o  o  o  o  o  o  o
o  o  o  o  o  o  o  o  o  o  o  o
x  x  x  x  x  x  x  x  x  x  x  x
x  C  C  C  C  C  C  C  C  C  C  T

Policy learned with double-Q-learning:
(x represent the steps taken by a greedy policy evaluation, T is target, C is cliff)
x  x  x  x  x  x  x  x  x  x  x  x
x  o  o  o  o  o  o  o  o  o  o  x
x  o  o  o  o  o  o  o  o  o  o  x
S  C  C  C  C  C  C  C  C  C  C  T

The policy learned from double-Q-learning is not the optimal-greedy, but a "safer" policy that walks the agent the furthest from the cliff. This policy is, in fact, identical to the one the book uses to present the difference between SARSA and Q-learning.

From these considerations, it would seem that double-Q-learning is learning an on-line policy instead of the off-line one that I was searching.
Could this be caused by an implementation error, or is this the expected behavior of the learning method?

This is my learning-step implementation of the double-Q-learning (in python):

# Take a step
if np.random.uniform() < 1.0-epsilon:
    action = np.argmax(Q1[state]+Q2[state])
else:
    action = np.random.randint(0, env.action_space.n)
next_state, reward, done, _ = env.step(action)

# TD update
if np.random.uniform() < 0.5:
    next_best_action_Q1 = np.argmax(Q1[next_state])
    Q1[state][action] += alpha * (reward + discount_factor * Q2[next_state][next_best_action_Q1] - Q1[state][action] )
else:
    next_best_action_Q2 = np.argmax(Q2[next_state])
    Q2[state][action] += alpha * (reward + discount_factor * Q1[next_state][next_best_action_Q2] - Q2[state][action] )
state = next_state

Q1 and Q2 are initialized to zero value for all pairs (state, action).
The policy used for the action selection is epsilon-greedy on the sum of the value estimates Q1 and Q2.


texts: Is this an instance of a well-known problem?

texts:
Context

I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I would like to get some feedback. Below you will find an abstract version of the problem.

The Problem

Input:

A bag of colored balls. A ball may have many colors (e.g. red, blue and yellow) or only one (e.g. green). Each ball has also a score. Since we are talking about a bag, elements may be repeated.
A set of colored boxes, one per color. Each box is labeled with a natural number.

Problem: each colored box must be filled with the exact amount of balls specified by its label.

Constraints:

The color of the balls in a box must match the color of the box (e.g. a green ball goes in a green box).
A ball of many colors can be assigned to a box of any of those colors (e.g. a ball that is both red and green can either go in a red box or in a green one).

The solution to the problem can be represented by the following information: for each box, a list of the balls it contains (a ball is represented as a list of colors and a score).

Output of the algorithm: the solution with the highest score. The score of a solution is the sum of the scores of all balls in the boxes (of course, there may be many solutions, but in that case we just pick one of them).

Current research

Somehow this problem makes me think of Sudoku, which is an instance of the exact cover problem. However, I haven't been able to come up with a way to model this problem in terms of exact cover and am afraid I may be missing a more straightforward approach.

As suggested in the answers, another possibility would be to model this using max-flow. However, this approach is unable to generate all possible solutions such that each box is filled to its capacity. Furthermore, the max flow value is known to be the sum of the capacities of the boxes (it is assumed the number of balls is large enough for this to happen).

Questions

Is this an instance of the exact cover problem? If yes, how would you model it in terms of exact cover? If no, is it an instance of any other well-known problem?


texts:
I am trying to understand the concept of NRU from the following link. I have got some problem in understanding the text below:

NRU page replacement Algorithm

  If the hardware does not have these bits, they can be simulated as
  follows. When a process is started up, all of its page table entries
  are marked as not in memory. As soon as any page is referenced, a page
  fault will occur. The operating system then sets the R bit (in its
  internal tables), changes the page table entry to point to the correct
  page, with mode READ ONLY, and restarts the instruction. If the page
  is subsequently written on, another page fault will occur,
  allowing the operating system to set the M bit and change the page's
  mode to READ/WRITE.

I have bolded the text. I have two problems: Page fault occurs if the page is not in memory but the above text says that
(a)the page fault occurs at the time of modifying or writing the page? I can’t understand that.
(b) Also I cant understand the text “, allowing the operating system to set the M bit and change the page's mode to READ/WRITE.” What is meant by READ/WRITE? If we are setting the M bit then it should be WRITE mode only? Why the text says READ/WRITE mode.
Somebody please guide me.


texts: Integer Knapsack Problem - No duplicates Allowed

texts:
In the bounded Integer Knapsack problem, we are given N items of sizes S1 through SN, having values V1 through VN. The problem requires us to find the maximum value that can be attained for a given capacity C, provided we cannot use an already used item twice.

In their book, Introduction to Algorithms, the authors have mentioned that for Dynamic programming to be applicable we MUST have "independent" subproblems. That is, the solution to one subproblem should not affect another subproblem. They have illustrated this through the "Longest-Path-Problem" in which they mention that once we solve a subproblem of finding the longest path from 'A' to 'B', for solving another subproblem, we would not be able to use the vertices used in the longest path from 'A' to 'B' and hence the subproblems are not independent.

Doesn't the same argument apply here as well - If we solve a subproblem of filling a smaller knapsack of capacity c < C, we cannot use the items used in filling 'c', in solving other subproblems.

I am new to dynamic programming - apologies if my question appears to be stupid.

Thanks.


texts: Is machine learning all about statistical regressions at its core?

texts:
For the past several months I've been interested in some Machine Learning and I can't help but notice that nomatter what kind of learning algorithm I'm using - at its core lies a simple polynomial or logistic regression. Today I went back to the most basic definition that I could find:

  Machine learning, a branch of artificial intelligence, concerns the
  construction and study of systems that can learn from data.

The fact that we're creating mathematical hypotheses based on data ALWAYS means that you're doing some kind of statistical regression ?

If I'm wrong, can you please provide an example where this doesn't hold true.


texts:
For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language
  $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{2}$ and $|\alpha| \le |\beta|$}\}.$$

  1) If $L_{1}$ and $L_{2}$ are CFL then is $L_{1} \operatorname{op} L_{2}$ always CFL?

  2) if $L_{1}$ and $L_{2}$ are regular languages then is $L_{1} \operatorname{op} L_{2}$ always CFL?


texts: "Immediate" method of translating arbitrary mutable program to equivalent unmutable program?

texts:
Consider the following program in "mutable style":

x=1
x=f(x);
x=f(x);

We can rewrite this in "immutable style" without changing the higher-level structure of the program:

x1=1
x2=f(x1);
x3=f(x2);

We turned it into an immutable style program by only making "local changes": We simply took the mutable variable $x$ and changed the program wherever $x$ appeared to make it immutable.

Question: Can we in general turn an arbitrary mutable program into an immutable program by only making local changes, so that the higher level structure of the program stays the same?

Obviously this will depend on the language. You may assume any language features you want. e.g. this answer talks about monads (though it's not clear to me whether they can always be used to translate programs using only local changes).


texts:
I have thousands of times series of different length and different time. I want to group them together so that I know the optimal ones to pick as input for a ML algorithm and to document how they are related. Those times series are from stations, some of them inactive and some still active.

My goal would eventually be to use data from active stations in the cluster in order to model the inactive station by assuming that the correlation of the signal will stay the same in time.

I am able to get the euclidean distance and a distance matrix ( used for DTW) for series that overlap but the issue is that most of them will not overlap together. So if I summarize the distance value and put it into a global distance matrix I will have a sparse distance matrix.

I know that hierarchical clustering can deal with data considering only their distance to each other but the distance matrix may contain only finite values (in the scipy version) and adding any sort of fake distance values will greatly affect clustering.

I am aware that DBSCAN might be my only option since I only have sparse distance measure and that any other approach with the raw data will not be possible due to their varying total length and their varying start and end period.

Is DBSCAN the only solution to these types of problems or are there other algorithms or methodology that can cluster using only sparse distance data ?


texts: Doesn't a quantum algorithm being deterministic contradict the superposition principle?

texts:
How can the EQP quantum complexity class exist? I mean, doesn't the superposition principle imply it is not possible to know with probability 1 whether a quantum algorithm will return a solution?

For if a quantum computer’s state is in superposition, quantum measurement implies the state we obtain when we read the computer's state is random - with the probabilty we will obtain any particular state being based on its probability amplitude at the time of measurement. Thus unless some state has probability amplitude 1 (which would mean the system wasn't in superposition, so can't have been a quantum algorithm, as any quantum algorithm must use superposition), we cannot know whether we will obtain a solution state at any quantum computation's completion.


texts: Time complexity of a classical version of Shor's algorithm

texts:
I'm sorry if this question seems too naive.
I've read the Shor's algorithm of factoring big number using quantum computer on Wikipedia. It says,the key step is to find the cycle of the function defined on positive integers:f(x)=a^x mod N, where a and N are positive integer,and N is very large.

What I would like to do is to analyze the time complexity of this key step using a classical computer.I tried the following: Wikipedia's page on modular exponentiation, I see f(x_0) takes O(N),(or less),and let x_0 = 1 to N takes N*O(N)=O(N^2),which is enough to find the cycle of f(x). This lead to the conclusion that the whole factoring algorithm is in polynomial time on a classical computer,which is not the case as far as I know.

So I must be wrong somewhere.Thanks for any help.


texts: Need help understanding textbook solution

texts:
I am studying for my final exam in coding-theory class, and as textbook provides poorly written solution to the exercise question, I decided to ask the question here, hoping for more clarification.

Question:

  If $C_1$, $C_2 \subseteq V$ are linear codes, with generator matrices $G_1$, $G_2$
  and parity-check matrices $H_1$, $H_2$, explain how to find a
  generator matrix for $C_1 + C_2$ and a parity-check matrix for $C_1 \cap C_2$.

Textbook solution:

  Form a generator matrix $G$ for $C_1 + C_2$ by adjoining the rows of
  $G_2$ to $G_1$ and then using elementary row operations to eliminate
  linearly dependent rows. A similar process with the rows of $H_1$ and
  $H_2$ gives a parity-check matrix $H$ for $C_1 \cap C_2$.

Clarification: My question is by word "adjoining", solution is referring to addition of two matrices or adjudicating them. Also, what is definition of "linearly dependent row"? If you could provide an example, it would be great.

Note:
I really don't like asking this type of question but combination of unhelpful professor and awful textbook made me to do this.


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

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


texts: set of Kolmogorov-random strings is co-re

texts:
given  RC = {x : C(x) ≥ |x|} is a set of  Kolmogorov-random strings.

How can I show that  RC  is co-re

I have been reading this paper What Can be Efficiently Reduced to the
Kolmogorov-Random Strings? which just says that we know that by Kum96 we know that RC is Co-re

I was not able to find the proof of how that is proved


texts:
While creating an algorithm, the following question came up:

  In uniform cost, what is the time cost of a process that creates a thread?

Is there a difference between creating a thread in a thread pool vs creating a thread in runtime?

I know these questions should be self-explanatory, but I cannot seem to find an answer.


texts: How to determine the max offset of a value, given the range, step size and amount of steps

texts:
Given

The starting and the end values of X
The maximum step (maximum delta)
Exact amount of steps

I need to determinte the maximum and the minimum possible values that X could become during this chain of changes and still make it from the start value to the end value with the steps that are less or equal to the maximum step value.
E.g. for data:

X_start = -10; X_end = 1;
MaxDelta = 7;
MaxSteps = 4;

The answer would be: Max = 4; Min = -11;
Sequences:
−10 → −3 → 4 →1
−10 → −13 → −6 →1
P.S. There is no need to generate such sequences, only the max and min values.
I have been thinking about the ways to do it efficiently and I am stuck. I have an idea that a binary search might be useful.
Any help/tips/suggestions would be much appreciated.


texts: What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input value; so how do we explain this shift from exponential to polynomial?


texts: Prove that the union of multisets is idempotent

texts:
I am struggling with a proof from my discrete mathematics class. We have to prove that multiset union is idempotent, i.e. $M \sqcup M = M$, where $\sqcup $ denotes the union of multisets.

We have defined multiset union (using lambda notation) as $M_1 \sqcup M_2 := \lambda x : X \cdot M_1(x) + M_2(x)$, which means that the union operated on a value will output the number of times the value appears in their union. However, if we apply union to the same set, won't the number of times a value appears in the union be twice that of the multiset on its own? How do I go about proving this?

Edit: Is this even correct? Might there be a mistake in the book?


texts: Are if statements avoidable is we define a program according to explicit state transitions?

texts:
This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation.

Consider a program that manages a single bank account (for the sake of simplicity). The bank account could be defined as something like

Account
{
    int balance; // current amount of Money

    boolean withdraw(int n)
    {
       if (balance >= n)
       {
           balance = balance -n;
           return true;
       }
       else
           return false;
    }

    void deposit(int n)
    {
       amount = amount + n;
    }
}

Since the program has no way to known in which state it currently is unless it performs validations using if statements, as in the withdraw operation, if statements are unavoidable.

However, over the course of time, the program will pass through a finite set of states that can be known beforehand. In this particular case, a state is defined solely by the value of the balance variable, hence we would have states: {balance = 0 , balance = 1, balance = 2...}.

If we assign each state a number, say state {0,1,2,....} with a 1-1 correspondence to the above set of states, and assign to each operation a number identifier as well (say deposit = 0 and withdraw = 1), we could model the program as an explicit transition between states and therefore remove every if statement from the code.

Consider that state = 0 is the state where balance = 0 and we want to perform a deposit of 50 dollars, if we coded every single possible execution of the deposit function, we could just define the deposit function as

void deposit (int n)
{
   deposit[state][n]; // index deposit instance for state = 0, amount = n;
}

deposit[][] would be a matrix of pointers for a set of functions that represent each possible execution of deposit, like

deposit[0][0] -> balance = balance + 0; state = 0;
deposit[0][1] -> balance = balance + 1; state = 1;

....

In the case of withdrawal, it would be like:

boolean withdraw (int n)
{
    // index withdraw instance for the current state and amount=n
    return withdraw[state][n];
}

withdraw[][] would be a matrix of pointers for a set of functions that represent each possible execution of withdraw, like:

withdraw[0][100] -> return false; state = state;
...
withdraw[200][100] -> balance = balance - 100; state = 100; return true;

In this situation, the program that manages the single bank account can be written without using a single if statement!

As a consequence however, we have to use A LOT more memory, which may make the solution unreasonable. Also one may put the question of how did we fill the deposit[][] and withdraw[][] matrices? By hand? It somehow implies that a previous computation that used ifs as necessary to determine and possible states and transitions.

All in all, are ifs fundamental or does my example prove that they aren't? If they are, can you provide me an example where this does not work? If they are not, why dont we use solutions like these more often?

Is there some law of computation which states that if statements are unavoidable?


texts: There could not be an edge from u to v in a DAG, if w is before v in a topological order

texts:
I am trying to prove that given a DAG. There exists a valid topological  ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post visit order satisfies the condition of topological order.
How do I construct a proof?


texts:
I'm looking at the following explanation of monotonic queues and their applications in problem solving.

Monotonic Queue Summary

I have a reasonable understanding of this data structure and the problems described in the post. However, i'm struggling with the following "recurrence relation"

Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

I don't completely understand this formula. It looks like a recurrence relation but seems to to be in reference to the underlying array.
I can't seem to see if the previous array range
(j to k) is referring to a portion of the array or a portion of previously solved sub-problems.

I'm not sure what the base case is and it seems like the answer is the minimum value in this array range plus some constant. I don't see how this solves the problems above.

Am I looking for too much precision in this statement or am I missing something?

The following seems more intuitive

Any DP problem where DP[i] = smallest(prefix_sums[j:k]) where j < k <= i and prefix_sums[k] - prefix_sums[j] >= K


texts:
I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph.

I want to find subgraphs $G_1,G_2, \dots,G_n$ of $G$ such that

they do not overlap (i.e. don't share any nodes)
each two nodes in a subgraph are connected by an edge, i.e. $\forall i \forall n,m\in V_i$ then $\{m,n\}\in E_i$ where $G_i=(V_i,E_i)$.

My question is: How to solve this problem? Is there any specific name of this problem?

Edit: The graph I am dealing with is very sparse. Coloring based approximations may not work as the complement graph would be huge (not able to store it in memory).


texts: Estimating the time until we obtain five-in-a-row?

texts:
Consider the following random process.  We have a $10\times 10$ grid.  At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker in that grid cell.  As soon as we have five contiguous markers in a line (in a row, column, or diagonal), we stop.

I'm given a grid containing some markers in some positions, and I'd like to estimate how long until the process stops if we start from that configuration (i.e., the number of additional time steps until five-in-a-line occurs).  I would be happy with any reasonable metric for that: e.g., the expected time until it stops, or the value $t$ such that there's a probability $0.5$ that the process will stop in $\le t$ time steps.  I'd be happy with an estimate of any such metric.

Is there any efficient algorithm to estimate this metric, given a configuration where some markers have already been placed?  I'm hoping for something faster than random simulation (repeatedly simulating the process and computing an estimate based upon the resulting empirical distribution).


texts:
I have a very simple quantum algorithm:

Let's start with two qubits in the state $|00\rangle$. I apply a Hadamard gate to the first one. Then I apply a CNot gate, with the first one as a control. Then I apply a Hadamard gate to both of them.

I think I should end up with with two qubits 100% in the $|00\rangle$ state. However, I tested this algorithm on two different simulators (QuantumPlayground and Davy Wybiral's), and the output of both was:

$$ 0.707\,|00\rangle ;\ 0.707\,|11\rangle\,. $$

Where did I go wrong?


texts: Computation is effectively computable in theory and in practice

texts:
My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice?

In trying to understand these concepts further, I have a couple of sub-questions as well:

Is there a relationship between a computation being EC in theory and being EC in practice? (It seems just by taking the usual meaning of the words, EC in practice should imply EC in theory.)
Is there an example of a computation that is EC in theory but not EC in practice?
How about EC in practice but not EC in theory?

Either explanations or links to where these explanations may be will be helpful.


texts:
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\theta_n\ldots d\theta_2 d\theta_1
$$

whose intervals are defined by
$$
\begin{align}
I_1 = [0,1] \\
I_i = [\max(c_i,\theta_{i-1}),1] , 2\leq i\leq n
\end{align}
$$

and the $c_i \in [0,1]$ are predefined rational constants. Given a rational $v\in [0,1]$,

  is deciding if $J=v$ NP-hard?

Informally , each $\max$ in the lower limits of the intervals leads to a two-way split in evaluating the integral, and thus to $2^{n-1}$ integrals that sum to $J$.


texts: Regular language with number of a's same as number of b's

texts:
L = { x^n y^n / x,y belongs to (a+b)^* , number of a's in x = number of b's in y and n > 0}

According to me it's regular because for any string $w$ belongs to $(a+b)^*$, we can divide the string into 2 parts $x$ and $y$ with $n=1$ .

Is my reasoning correct?


texts: Algorithm for b-matching on bipartite graph

texts:
I have a bipartite graph, where I want to assign nodes in Left set to Right set of nodes. There is a "b" constraint, which limits the maximum possible node degrees on the Right set.
Since it is a classic problem, I expected to find a lot of algorithms on it, but was not successful. Any ideas how to solve it?


texts: Is Inductive Logic Programming approach applicable to general theories (not just sets of Horn clauses)?

texts:
Inductive Logic Programming (https://en.wikipedia.org/wiki/Inductive_logic_programming) find hypothesis theory H for background theory B and set of examples E. ILP algorithms and implementations usually expects, that H, B, E are logic programs - set of Horn clauses and not general FOL or HOL theories. This approach is generalized to the HOL logic programs as well, e.g. in http://andrewcropper.com/pubs/ijcai16-metafunc.pdf.
My question is - are there efforts to formulate induction/ILP for general theories. Apparently, the algorithm does exist and the problem is undecidable, but still - are there some heuristics, some approximate approaches, some more or less rigorous work for such generalization? Both - for full FOL and HOL?
E.g. references wiki articles mentions the method of inverse entailment - I see that that approach is general enough - it requires the computation of the most conscise (e.g. Occams razor principle - with the minimal Kolomogorov or other complexity) set of consequences in some depth.
Actually - ILP may be the Holy Grail of AI: 1) it can learn general policies from the specific policies and hence - implement generalization and transfer learning, e.g. in reinforcement learning; 2) it can learn the program which from background knowledge computes the set of input-output patterns (in more or less general form) and hence - solve the program synthesis task.


texts: Physically indexed virtually tagged cache

texts:
PIVT cache is indexed physically so address translation using TLB is needed to get into cache and we use virtual address as the tag for comparison .

I read that homonym is a problem which is caused when same VA maps to 2 different physical addresses and PIVT suffers from homonym.
Source :- https://stackoverflow.com/questions/20787522/cache-addressing-methods-confusion

My question is, if we have 2 processes with same VA mapping to 2 different physical addresses (as both processes have their own page tables), then even though the tags are same, but the physical addresses are different so there should not be any problem. So, how can homonym occur in PIVT ?


texts: Rules language / DSL expressivity measure

texts:
Languages to express domain rules are quite diverse from very simple and inexpressive to Turing-complete programming languages. If we consider developing some DSL (domain-specific language), is there any generally useful scale (Chomsky hierarchy comes to mind as an analogy, as well as Description Logic "letters", like SROIQ) to classify the domain DSLs?

Of course, it is naiive to expect full order, but at least which are some commonly used partial order classes of expressivity? And it would be nice to know what is the correct terminology for such expressivity scale.

Of course, lower bound of algorithmic (time, space) complexity can be applied the rules/inference engine itself (eg, satisfiability checking), but this belongs more to implementation details and engineering trade-off than to the model of the domain itself.

Maybe, I am wrong that such specific domain classification does exists at all, and practice as well as theory lives with measures, which I mentioned above. However, even for boolean formulas there are studied measures of complexity, so why not other theories?

Some discussion, which however does not help me, found here: https://www.linkedin.com/grp/post/81971-75677017 Also, this https://stackoverflow.com/questions/2427496/what-do-you-mean-by-the-expressiveness-of-a-programming-language is relevant. To be clear, I stick with Wikipedia definition of expressivity here, and practical side of that more than theoretical one.

Expressivity in this question is an ability to model some domain with enough precision for some given purpose. That is, it can be said, "we need at least DSL expressivity D for the model of this domain for our application, the level C is not enough."


texts: Optimizing hash table for common subset of keys?

texts: Are there variants of hash tables that take advantage of the likely distribution of key values? For example, if I'm using utf-8 encoded unicode strings as identifiers in a compiler but expect the majority of them to fit into ASCII, can I optimize for that use case?


texts: Gradient descent vs. Newton's method: which is more efficient?

texts:
Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both gradients and Hessians.

However, gradient descent generally requires many more iterations than Newton's method to converge within the same accuracy.

My question, then, is:

Assuming they both converge, in terms of the number of elementary floating-point operations, which is usually faster:  Newton's method or gradient descent?  Why?


texts: Why are different logarithms in the same Θ even thought their difference diverges?

texts:
As I have read in book and also my prof taught me about the asymptotic notations

The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large value of $n$.

So from here my confusion is-

$2^n=O(3^n)$ and $\log_2 n=\Theta(\log_3 n)$

First relation is clear to me and second relation is confusing me.Though I derived $\log_2 n$ and $\log_3 n$ to same base and noticed that $\log_2 n=\log_{10} n/\log_{10} 2$ and $\log_3 n=\log_{10}n/\log_{10}3$. So In both constant factor can be removed. So second relation is also OK.

Still there remain a doubt that when I see the graph plot of $\log_2 n$ and $\log_3 n$, $\log_2 n$ is always above $\log_3 n$ and grows faster than $log_3 n$ i.e the difference of log values increases as n increases. Then I got more confused when I saw the graph plot of $x_1=y$ and $x_2=2y$ in which again $x_2$ is above $x_1$ and difference is increasing b/w them as $y$ increases.

So now I want to know .How do I distinguish from graph about the asymptotic relations of the function. In what sense they say one function is upper bounded by the other though 2 lines with different slopes also following this.Why don't we say one line is upper bounded by the other.We only say they are related by $\Theta$.

Please help me understand this concept.


texts:
An integer n > 0 is called a perfect power if there are integers a, b
≥ 2 for which n = a^b. Show that the set of perfect powers belongs to
P.

Is the time complexity to this decision problem O(n^2)? These are the polynomial computations involved to this problem:
Given a number n, if at all it can be written as a^b (b > 1), then b<log(n)+1: O(log n), which is equal to O(n) in polynomial time.
And for every fixed k, checking if there exists a a with a^b=n can be done using binary search: O(log n), which is also polynomial, O(n).
So, I guess the total running time is also polynomial: O(loglog n) -> O(n^2)?


texts: Pumping lemma for context-free languages - Am I doing it right?

texts:
I have an exam coming up in three days, and there's a thing that I really need to be able to completely understand - that is, of-course, pumping lemmas for CFL. I know how to do prove that a regular language is not regular using PL, but for CFL it's a bit more variables, and I am not entirely sure how to split a string. Below, I will provide with an exercise and my attempt. I want to know, am I doing this correctly and if not, what do I need to do to make it correct?
The exercise (although quite similar to the previous question I asked, that question was for regular language and not CFL - in short they are two different questions)

Show, using pumping lemma, that $L2 = ${ $ 0^m 1^k 2^n | n = km $} is not context-free

My attempt goes as following:
If L2 is context-free, then there exist a constant $P$ such that $ S \in L2 $ and $|s|\ge P $ which implies that there exist strings uvxyz such that the following are satisfied:

$(1) uv^ixy^iz \in L2 $ for every $ i \ge 0 $

$(2) |vy| > 0 $

$(3) |vxy| \le P$

We must first assume that $L2$ is context-free
$L2$ must have a Pumping length $P$
Must also take strings $0^P 1^P 2^{p^{2}} $ (since n = km)

There are 3 cases

case 1) VXY does not straddle a boundary, belongs to just one
So we have $0^P 1^P 2^{P^{2}}$, let's split that into $UVXYZ$,

$U = 0^P$,  $ V = 1^r $, $ X = 1^t $, $ Y = 1^{P-r-t}$, $Z= 2^{P^{2}} $
and then we select $i = 2$, which gives us
$uv^2xy^2z = 0^p 1^{2r} 1^t 1^{2p-2r-2t} 2^{p^{2}} =  0^p 1^{2p-t} 2^{p{^2}} \notin L2$

case 2) VXY straddles the first boundary;
like above, we split into $uvxyz$ where
$u = 0^r $
$v = 0^{p-r} 1^t $
$x = 1^r $
$y = 1^{p-t-r} $
$z = 2^{p{2}} $

if we, yet again, select $i = 2$

$uv^2xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{r} 1^{2p-2t-2r} 2^{p{2}} = 0^{2p-r} 1^{2p-r} 2^{p{2}} \notin L2 $

case 3) vxy straddles the second boundary;
again, like above we split the string into 5 parts $uvxyz$ where
$ u = 0^p $
$ v = 1^t $
$ x = 1^r $
$ y = 1^{p-t-r} 2^t$
$ z = 2^{p{2} - t} $

if we select $i = 2$
we get $uv^2xy^2z = 0^p 1^{2t} 1^r 1^{2p - 2t - 2r} 2^{2t} 2^{p{2}-t} = 0^p 1^{2p-r} 2^{p{2}+t} \notin L2$

Thus we have contradictions for all three cases, which concludes that the language is not context-free!

My general question is am I selecting a string correctly? I.e. does it have to satisfy $|vxy| \le p$ in-order for the $uv^ixy^iz $ where $ i = 2 $ to work? OR must $vxy$ be chosen so that the length is $\le p$? Have I missed cases?

Thank you in advance!


texts: Algorithm to find a shortest past under a special condition


texts: Utility of D latch/flip-flop and how it differs from an SR latch/flip-flop

texts:
I understand that in a D latch, whenever the clock signal is high, Q matches D, and while the clock signal is low, it holds the previous state of D. For a D flip-flop, Q will hold whatever value D is at the exact moment C goes high, and will hold that same state until C goes high again. I am able to draw the clock diagram and identify these circuits. But I am not understanding the purpose of these components in a high level context.

What exactly does the D latch and D flip-flop do? (Differences and similarity)
From my understanding, it is to be able to "store" a bit value, but if that's the case, why not use an SR latch?

Edit: I have seen the following post. However, my question is a little more specific. I am asking specifically about a D latch/flip-flop. I also want to be able to differentiate how this is different from a SR latch, since it seems that their descriptions seem to do the same thing.


texts: Data Structures for Non-Orientable Manifolds

texts:
I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, but not limited to, Catmull-Clark Subdivision, Offsetting, Minkowski Addition and Minimal Surface. I know that I cannot use Half-Edge Data Structure because it can only be used for orientable manifolds.

I am currently using Winged-Edge Data Structure. This is a very obvious choice, easy to program and reason. I am asking whether there are better, newly invented data structures; or are there any data structures that are better for certain niche use cases (that I might be interested)? I would be more than happy if you could point me some research papers.

Additional Information:

I only need to represent 3-dimentional manifolds.

Thanks!


texts: How to uniquely encode a vector of non-increasing positive integers

texts:
Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the following conditions,

The result of encoding is unique, i.e. the encoding of two different vectors cannot be the same.
The result of encoding has the same order as the dot-product of A with  the vector $[1, \cdots, n]$, i.e., $A \cdot [1, \cdots, n] > A' \cdot [1, \cdots, n] \Rightarrow e(A)>e(A')$.

I was wondering if such encoding exists. I tried a couple of options such as $e(A)=A \cdot [2^1, \cdots, 2^n]$, but it did not work. I am not sure if considering an irrational number such as Euler's instead of 2 would work, i.e. $e(A)=A \cdot [e^1, \cdots, e^n]$.

P.S. Of course, one way is using prime numbers, but this way is computationally very expensive and I want to avoid that. So, I prefer a way that does not involve calculating prime numbers and such computationally-intensive values.


texts: How does software interact with the cpu in the fetch execute cycle?

texts: As the question suggests, is there any interaction or relationships between any sort of software and the cpu during the fetch-execute cycle?


texts: The PDA have to finish reading the input?

texts:
I have PDA which has final state that accept 'c' char, and there isn't any cross to other state.
The input abca will accept, because there is 'c', or the PDA would stuck?


texts: Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

texts:
I'm having a small issue with wikipedia's proof that $RP \subseteq NP$:

An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.

My problem lies in the following statement: "...accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept"
My question is: for a language $L \in NP$, wouldn't it only need one computation path for the non-deterministic TM to accept? Since, if $x \in L$, $P[T(x) accepts] >= 1/2$ with $T$ being the Turing machine that decides $L$.


texts: Arithmetical representation $F(x,y,z)\Longleftrightarrow (x+z)=y \lor (y+z)=x$

texts:
I am kind of confused which function $f:\mathbb{N}^2\longrightarrow\mathbb{N}$
is presented by $F(x,y,z)\Longleftrightarrow (x+z)=y \lor (y+z)=x$
I know that $f(x,y)=y-x$ is represented by $F(x,y,z)\Longleftrightarrow (x+z=y)\lor ((z=0)\land \exists w(x+w)=y)$
But the or symbol confuses me ... My guess was
$f(x,y)=max\{x-y,y-x\}$ but i think this is wrong due to a missing check in F(x,y,z)
For info:
An function $f:N^k⟶N$ is arithmeic representable when there is a arithmetic formula F with $F(x_1,...,x_k,m)⟺f(x_1,...,x_k)=m$


texts: Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

texts:
For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:
$$
\begin{matrix}
&
\begin{bmatrix}
1 & 1 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 0 & 0
\end{bmatrix}
&
\begin{pmatrix}
2\\2\\2
\end{pmatrix} = R
\\
C = &\begin{pmatrix}
3 & 3 & 0 & 0
\end{pmatrix}
\end{matrix}
$$
However, the row sum vector $R' = (4, 1, 1)$ doesn't form a match with $C$.
So given two vectors whose values are sorted in a non-increasing order $C_w$ and $R_h$, and whose accumulated sum is the same, $T = \sum_jc_j = \sum_ir_i$, how can I polynomically check if $C$ and $R$ form a matching because I can form a matrix $M_{h,w}$ having $C$ and $R$ as colum and row sum vectors respectively?
More specifically, in case it can help to make the check algorithm faster, in my specific case, C and R has the following properties:

$h \leq w$
The number of positive values of $R$ and $C$ is $> w$. For example, $C$, in the example, has two positive values and $R$ has three positive values, and it happens that $2 + 3 > w = 4$.


texts: How does a compiler infer a value's type?

texts:
From A Swift Tour — The Swift Programming Language (Swift 5):

var myVariable = 42
myVariable = 50
let myConstant = 42

  A constant or variable must have the same type as the value you want to assign to it. However, you don’t always have to write the type explicitly. Providing a value when you create a constant or variable lets the compiler infer its type. In the example above, the compiler infers that myVariable is an integer because its initial value is an integer.

How does this work?


texts: Cross link suggestion algorithm that distributes and spans all links as fast as possible without loops

texts:
I am implementing a topic suggestion system to a website. The aim is to add links to the left panel of each topic. For example, I opened the topic named "topic1", left of the page should show 5 additional topic links, say "topic48", "topic1453", "topic1905", "topic35", "topic63". Objectives are as follows:

1) Distribute all topics equivalently, so that topics are referenced by almost the same number of other topics. For example, every topic is referenced minimum 10, maximum 15 times.

2) Regardless of which topic I started to display, all topics should be suggested as shallow as possible. For example: let's say I have 10 topics with ids [1,2,3,4,5,6,7,8,9,10] and we need to suggest 3 topics for each topic. The suggestion tree should be as follows:

                            3
          |                 |                   |
          8                 4                   6
      |   |   |         |   |   |           |   |   |
      1   7   9         2   5   10         ...  ... ...

As you can see, all topics should be suggested as shallow as possible.

3) There should not be such loops:

topic1 -> topic2, topic7, topic9

topic2 -> topic1, topic7, topic9

topic7 -> topic1, topic9, topic2

topic9 -> topic1, topic2, topic7

Is there such algorithm(s) to provide that functionality. Any suggestions?


texts: Rigorous Definition of a Complexity Class

texts:
From Wikipedia, "Complexity classes are sets of related computational problems. They are defined in terms of the computational difficulty of solving the problems contained within them with respect to particular computational resources like time or memory. More formally, the definition of a complexity class consists of three things: a type of computational problem, a model of computation, and a bounded computational resource."
Class P and NP seem to fit this definition exactly.
However, when I look at classes like #P: it seems to me just like a set of related computational problems put together that have not been assigned a complexity class yet, as we do not define time and space resources for them.
I am wondering: in theory, can I just take a set of two problems and call it a complexity class (even it if may be a useless one)?. Is there a rigorous definition to what constitutes a complexity class? If so, what is it?


texts: Computational power of nondeterministic type-2 min-heap automata

texts:
I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

This question concerns the computational power of type-2 min-heap automata, which were suggested by Raphael as a more natural kind of computing device. The class of languages which can be accepted by such automata is a proper superset of the set of context-free languages; which leads me to my question.

  Is $HAL_2$ (the set of languages accepted by nondeterministic type-2 min-heap automata) a proper subset of $CSL$ (the set of context-sensitive languages), or not? Note that it is already known (shown by Raphael in the linked question) that there are $CSL$ languages not in in $HAL_2$.

This is one of the last questions I intend to ask about these automata. If a good answer can be found to these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.


texts: Why two phase locking requires second phase not able to acquire lock for another object?

texts:
I wonder why two phase locking is designed in a way that as long as you release a lock, you cannot acquire any lock anymore, even for a lock on a different database object.
Can't the scheme be relaxed to as long as you release the lock for an object, you cannot acquire the same lock again? So you release the lock on an object when you won't touch it again?
Is there any anomalies in this way?


texts: Rice theorem, the proof of the part when the empty language belongs to the property

texts:
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the proof the Rice theorem as shown.
$L_u$ => Language accepted by universal turing machine
$P$ => property of a regular language
$L_P$ => set containing the codes of the turing machines which accept those languages in $P$
Theorem : (Rice's Theorem) Every nontrivial property of the RE languages is undecidable.
PROOF: Let $P$ be a nontrivial property of the $RE$ languages. Assume to begin that $\phi$, the empty language, is not in $P$. we shall return later to the opposite case. Since $P$ is nontrivial, there must be some nonempty language $L$ that is in $P$ . Let $M_L$ be a $TM$ accepting $L$. We shall reduce $L_u$ to $L_P$, thus proving that $L_P$ is undecidable, since $L_u$ is undecidable. The algorithm to perform the reduction takes as input a pair $(M,w)$ and produces a $TM$ $M'$. The design of $M'$ is suggested by Fig; $L(M')$ is $\phi$ if $M$ does not accept $w$, and $L(M')$ = $L$ if $M$ accepts $w$.

$M'$ is a two-tape $TM$. One tape is used to simulate $M$ on $w$. Remember that the algorithm performing the reduction is given $M$ and $w$ as input, and can use this input in designing the transitions of $M'$. Thus, the simulation of $M$ on $w$ is "built into" $M'$; the latter $TM$ does not have to read the transitions of $M$ on a tape of its own. The other tape of $M'$ is used to simulate $M_L$ on the input $x$ to $M'$ , if necessary. Again, the transitions of $ML$ are known to the reduction algorithm and may be "built into" the transitions of $M'$ . The $TM$ $M'$ is constructed to do the following:

Simulate $M$ on input $w$. Note that $w$ is not the input to $M'$ rather, $M'$ writes $M$ and $w$ onto one of its tapes and simulates the universal $TM$ $U$ on that pair. If $M$ does not accept $w$, then $M'$ does nothing else. $M'$ never accepts its own input, $x$, so $L(M') = \phi$. Since we assume $\phi$ is not in property $P$ , that means the code for $M'$ is not in $L_P$ .

If $M$ does not accept $w$, then $M'$ does nothing else. $M'$ never accepts its own input, $x$, so $L(M') =\phi$. Since we assume $\phi$ is not in property $P$ , that means the code for $M'$ is not in $L_P$.

If $M$ accepts $w$, then $M'$ begins simulating $M_L$ on its own input $x$. Thus, $M'$ will accept exactly the language $L$. Since $L$ is in $P$ , the code for $M'$ is in $L_P$ .

Constructing $M'$ from $M$ and $w$ can be carried out by an algorithm. Since this algorithm turns $(M,w)$ into an $M'$ that is in $L_P$ if and only if $(M,w)$ is in $L_u$, this algorithm is a reduction of $L_u$ to $L_P$ , and proves that the property $P$ is undecidable.
We are not quite done. We need to consider the case where $\phi$ is in $P$ . If so, consider the complement property $\overline P$ , the set of $RE$ languages that do not have property $P$ . By the foregoing, $\overline P$ is undecidable. However, since every $TM$ accepts an $RE$ language, $\overline {L_P}$ , the set of (codes for) Turing machines that do not accept a language in P is the same as $L_{\overline P}$ , the set of TM's that accept a language in $\overline P$ . Suppose $L_P$ were decidable. Then so would be $L_\overline{P}$ , because the complement of a recursive language is recursive.
I could not understand the last paragraph in bold.


texts: Computer science problems related to music?

texts:
Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a scale or a tonality or general what is considered harmony in frequencies and physics, electromagnetism and waveforms.

Can you give examples of the area I want to know of?

For instance, given an algorithm that guesses a melody, how successful will the melody be in resembling an artist or likewise decision problem that could be feasible or what do you think?