texts: Proof that $P\subseteq NP$ without nondeterministic TM

texts:
I know the proof that using nondeterministic TM, but as I understood there is another proof without nondeterministic TM.
If you answer please write with as much details as you can.


texts:
If $A^2$ is regular, does it follow that $A$ is regular?
My attempt on a proof:

Yes, for contradiction assume that $A$ is not regular.  Then $A^2 = A \cdot A$.
Since concatenation of two non-regular language is not regular $A^2$ cannot be regular.  This contradicts our assumption.  So $A$ is regular.  So if $A^2$ is regular then $A$ is regular.

Is the proof correct?
Can we generalize this to $A^3$, $A^4$, etc...?  And also if $A^*$ is regular then $A$ need not be regular?
Example: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ is not regular but $A^*$ is regular.


texts: "Breadth course" problem – find maximum independent set given all maximal cliques

texts:
One of the undergraduate degree requirements at my university is that all Letters and Science students must take a "breadth course" in each of seven categories. If a course has multiple associated categories, you have to pick one; you can't satisfy multiple breadth requirement categories with a single course.

For example, while CHINESE 110A Introduction to Literary Chinese is both an "arts and literature" course and an "international studies" course, you can only use it for one of the two categories. If you then take COMLIT 156 Fiction and Culture of the Americas, which satisfies "arts and literature", you've now got both of the categories taken care of.

I'm trying to write a program that determines the maximum number of categories you can fulfill with a given set of courses. I suspect I can do this by creating an undirected graph as follows:

Each node of the graph represents a particular course applied to a particular category.
The graph has a clique for every category containing all of the nodes with that category, as well as a clique for every course containing all of the nodes with that course.

For the example case, we'd make a graph that looks like this:

Then, the number of requirements fulfilled would be the size of the maximum independent set of the graph.

Where I'm having trouble is in finding that maximum independent set. I'm aware that algorithms exist to find the maximum independent set of any graph in exponential time, but is there a more efficient algorithm I could use to take advantage of the fact that I already know all the maximal cliques?


texts: Need help understanding a derivation of "witnesses" for a Landau bound

texts:
So here's an excerpt from Foundations of Computer Science by Alfred Aho and Jeffrey Ullman[1]. I've also found basically the same material in a few other places, and also in my discrete math textbook, but this is clearest one I've seen:

  Example 3.2. Suppose we have a program whose running time is $T(0) = 1$, $T(1) = 4$, $T(2) = 9$, and in general $T(n) = (n + 1)^2$. We can say that $T(n)$ is $O(n^2)$, or that $T(n)$ is quadratic, because we can choose witnesses $n_{0} = 1$ and $c = 4$. We then need to prove that $(n + 1)^2 \leq 4n^2$, provided $n \leq 1$. In proof, expand $(n + 1)^2$ as $n^2 + 2n + 1$. As long as $n \leq 1$, we know that $n \leq n^2$ and $1 \leq n^2$. Thus $n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 = 4n^2$.

Even so, I get lost where it says:

$$
n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2
$$

I get that it's true, but it seems arbitrary. How/why did the expression get modified on the right side of the $\leq$ like it did? Couldn't they also have done this?

$$
n^2 + 2n + 1 \leq 4n^2 + 0 + 0
$$

Specifically, what rule did they apply to transform the expression $n^2 + 2n + 1$ into $n^2 + 2n^2 + n^2$?

http://infolab.stanford.edu/~ullman/focs.html


texts: Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

texts:
Let G = (V,E) be a unit-capacity graph with n vertices and m edges.

Let T denote all the spanning trees in G.

If we run Karger's algorithm, we will get a random spanning tree in T formed by the contracted edges, we denote this distribution of spanning trees by D1.

On the other hand, if we assign a random weight in (0,1) to each edge and compute a minimum spanning tree using Kruskal's algorithm, then another distribution D2 over T is obtained.

Show that the distributions D1 and D2 are identical.

I have no idea where to start. Any hint is helpful!


texts: Revisiting complexity of art gallery-like problem

texts:
In a question I had asked earlier, I was interested in knowing whether we could decide in polynomial time whether, for a directed graph $G$ with every one of its vertices belonging to an edge, a size-$w$ watch set, with $w$ at least half the number of vertices in $G$, exists (see the linked question). Several users showed that, in fact, such a polynomial time decider does not exist.

I'm interested in whether a polynomial time decider exists for a variant of this problem. Now, suppose that $G = (V,E)$ is an $n$-vertex directed graph with the property that every vertex in $G$ has an edge entering it. That is, for each vertex $v \in V$, there is an edge $(u,v)$ in $E$. With this in mind, consider the problem of deciding whether, for a given $w \geq 2n/3$, $G$ has a size-$w$ watch set. With the constraint that every vertex has an edge entering it, I'm not sure that we are able to reduce from arbitrary directed graphs, as Discrete lizard showed we could do in my earlier question. What I suspect is that any graph of this type must have a size-$w$ watch set, with $w \geq 2n/3$.


texts: Given CFG generates all words with equally many 0s and 1s

texts:
Here is an exercise from an introduction to computation class:

Show that the following context-free grammar $G$ generates the language $L$ of words over $\{0,1\}$ with an equal number of $0$s and $1$s:
$$
S \to \epsilon \mid SS \mid 0S1 \mid 1S0
$$

How should I prove that $L⊆ L(G)$ and $L(G) ⊆ L$?
I think I should start with the difference of 0's and 1's but have no clue where to start.


texts: Synchronisation and ordering in distributed systems

texts:
I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages and updating a data store based on those messages. Let's say 2 updates for a particular record enter the queue, one at t1 and the other at t2 (t2 > t1). Further, the t1 packet is consumed by a node n1 and the other one by n2. Now, what would happen if due to computational or network latencies, n2 processes the packet earlier than n1 and updates the data store. Since n1 has an older update, it should not update the data store.

One way I can think of, is to maintain a per attribute versioning of the record and generate a sequence number for each message based on which updates should be made. We could also use timestamps but we would run into issues if the clocks across the nodes drift.

Is there a standard universal way of tackling these sequencing issues? Is this what ZooKeeper does? Are there any interesting reading materials on this topic?


texts:
Let's say that I wanted to build a key to value associative map where the only requirement was that lookup times were fast.

Once built, the associative map would not allow inserts, deletes, or modifications, so is a static data structure.

What would the best algorithm be for making and using such a thing?

I'm interested to know if there is a provable "best solution", or if it's provably NP-Hard or similar.

Here are some ideas of my own:

Minimally Perfect Hash

My best idea would be to use minimal perfect hashing.  I would find a hashing algorithm that hashes the $N$ known inputs to $[0,N)$, that resulting value being able to be looked up in an array.

I would want to find the computationally cheapest (average time) hashing algorithm for my data set.

However, finding a minimally perfect hash function is a challenging problem already without wanting the computationally cheapest one.

Feature Based Indexing

Another thought I have would be to look at my input and find bits which are differing between items.  For instance, file paths may have a lot of the same characters in them, especially if they are absolute paths to the same deep folder.

I could find where the bits are that matter and make a tree of objects out of them.

The challenge here I think is that I would ideally want a balanced tree, and it might be hard to test all the permutations of bits that actually matter, to make the tree as balanced as possible.

I think Ideally, my hope is that the entire tree could go away, and I could instead take the bits that mattered and make some equation like "xor bit 2 against bit 3 and add bit 5" to come up with an index into an array.


texts: Do we need to read the input completely in Turing machine?

texts:
This question is motivated from the question $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$. I am wondering, how is it  possible to decide a language without reading the entire input. I have seen the similar situation in space complexity ( L and NL ,where we define new model of computation).

My model of computation is Turing machine (for e.g. see lecture note on Turing machine)

My question :  Do we need to read the input completely in Turing machine ?


texts: Need help understanding what co-recursively enumerable means

texts:
Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not halt on inputs in L.

So in this case would something "not in L" be nothing?


texts: What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?

texts:
During a lesson, our TA asked:

  What kind of languages can be recognized by a deterministic Turing
  Machine such that we can use only a tape portion that contains the input?

My thoughts:
my Theory of Computation book says that there is a special TM called linear bounded automaton (LBA) that corresponds to a non-deterministic Turing Machine that has a limited tape. Such machine recognize Context Sensitive languages.

So if i simulate the LBA behavior starting from a deterministc TM, may I recognize "deterministic"-Context Sensitive Languages?


texts: Is there a bound on possible Dead state in a minimized DFA

texts:
I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc?
Intuitively, I am thinking that it is at most one, because if other state is there from where accept state is not reachable, the minimization would merge the states, because it is serving no more purpose than the other dead state.
Is my intuition true?


texts: Can a NP problem be reduced to another NP problem?

texts:
I have three related questions which have been bothering me for a while now...

Suppose I have a problem $A$, which is in NP. Suppose there is another
problem $B$ in NP, can I reduce $A$ to $B$?
If it is possible, can this reduction be done in polynomial time?
Is it even meaningful (having any importance, in terms of complexity analysis) if we have a non-polynomial time reduction?

Help for these questions would be highly solicited!

Thanks in advance!


texts:
Prove: $P\ne BPP$ implies $P\ne NP$.

Obviously $P\subseteq BPP$ so the assumption is really $BPP\subsetneq P$. I'm trying to show the implication by contradiction. Let's assume that $P=NP$ and let's look at some language $L\in BPP$. Then, it has a proper probabilistic TM which decides it.

At first, I thought that I could just show some $NP$ machine which uses the $BPP$ machine but a relation between the two classes it not yet known, so it's probably not what I'm supposed to do.

We did learn Adleman's theorem and I think it could be used here (though we haven't define $P/poly$). Adelman's theorem claims that for every $x$ there's a $y$ s.t.

$$x\in A \implies M(x,y) = 1 \\ x\not\in A \implies M(x,y) = 0$$

so it boils down to the problem of finding such $y$, but I don't think this problem (finding $y$) is in $NP$ (or even possible)

Also, I understood that one can use the polynomial hierarchy theorem but we were not taught it.


texts: Implementation of logic function using a multiplexer

texts:
A question asks me to simplify the following boolean expression then use a multiplexer to implement it.

$$\overline{A}BC + \overline{A+B+C}+A\overline{B}\overline{C} + B\overline{C}$$

I evaluated the expression and got this result:

$$\overline{A}BC + \overline{C}$$

However, I stuck here because I cannot see the connection between this expression and the multiplexer. Can someone give some hint? Much appreciated :)


texts: concurrency control in real time database

texts: Can Lamport's Bakery algorithm be used for controlling concurrency in soft real time database system (case study of stock trading)?


texts: What is the maximum number of initial states in NFA?

texts:
It is well understood that DFA has only one initial state. However, in NFA, multiple initial states are possible. As in NFA, it is equivalent to having a separate initial state with epsilon-transitions to the multiple initial states. So, here I am looking for any clues to obtain the maximum possible number of initial states in NFA.
Thanks for sharing your help.


texts: Choose a specific regular language to prove a language is not regular

texts: I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot confirm if it is or not). I know of the pumping lemma, which I have used on very basic languages to prove they are not regular, but I'm not even sure where to begin on this one.


texts: Reduction of Hamiltonian cycle to Hamiltonian cycle & clique

texts:
I've been given a homework problem to prove that determining whether a graph G has both a Hamilton cycle and a clique of size k is NP-complete.

Based on this question, I know an "easy" reduction exists from Hamiltonian path to Hamiltonian path & clique (or someone has said it exists), and I assume that the same is true for reducing Hamiltonian cycle to Hamiltonian cycle & clique.

My thought is to somehow insert a clique of size k into G such that it's in the original cycle. (If I can make it lie in the path of the original cycle, it shouldn't disrupt the cycle, as all cliques have a Hamiltonian path through them.) But there are two problems with this approach:

I'm not sure how to insert a clique in such a way it can't create or destroy a cycle. I've tried:

Inserting the clique on an arbitrary edge of the graph (can result in a G' without a Hamiltonian cycle)
Adding k-2 vertices and creating a clique between them and two adjacent vertices in G (can result in G' without a Hamiltonian cycle)
Inserting the clique between input & output nodes connected to two different vertices on the original graph (can result in G' with a Hamiltonian cycle where G did not have one, if the points are arbitrary, or G' without a Hamiltonian cycle if inserted across adjacent vertices)

More generally--if I can find a way to insert a clique while preserving G's original Hamiltonian cycle--does this actually satisfy the iff requirement of the reduction? I don't feel like it does, because the existence of the clique in G' is in no way contingent on the existence of the Hamiltonian cycle in G.

Could someone give me a push in the right direction on this? I'm totally stumped on another way to approach it.


texts: Time complexity to find Median of Medians

texts:
I recently wrote my Grad school Admission test few days back and the following question appeared in the test.
There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ..., An contains 'n' distinct elements. There are no common elements between any two arrays. The worst case time complexity of computing the median of medians of A1, A2, ..., An is:

O(n)
O(n log(n))
O(n^2)
Ω(n^2 log(n))

Approach 1: Compute the median using Counting Sort for all arrays and then store the median values in a separate array. Once again apply Counting Sort on the newly created array having median values and compute the median.
Time Complexity = O(n^2)
Space Complexity = O(n)

Approach 2: Instead of Counting sort, use any other algorithm with constant space complexity, thereby yielding a total Time complexity of O(n^2 log(n)).

  According to space-time trade-off, a problem or calculation can either
  be solved in less time by using more storage space (or memory), or by
  in very little space by spending a long time.

Approach 1 favours time and Approach 2 favours space. I believe that space should be favoured as the size of Array will be very high on performing Counting sort when the range of values is high. Thus I marked Ω(n^2 log(n)) in test. However, my mentor and one my acquaintances say time should be favoured and O(n^2) is the correct answer. So, my question is whether to favour time or space?


texts: Are all prefix codes uniquely decodable?

texts: I can't think of any counterexample but I can't find any such statement on the internet or my textbook either. I know that for each uniquely decodable code, there exists a prefix code with the same average length.


texts: Purpose of randomization/derandomization in basic randomized algorithm for MAX SAT

texts:
In Sections 5.1 of The Design of Approximation Algorithms by Williamson and Shmoys, they describe a basic randomized algorithm for MAX SAT and how to derandomize it. The algorithm is just to assign each variable 1 (true) with probability 1/2 and 0 (false) with probability 1/2. In other words, sample uniformly at random from the space of all solutions. They show that this is a 1/2-approximation.
Then in Section 5.2, they describe how to derandomize it using the method of conditional expectations. (I won't describe the process here because it is not very complex and widely known I'm assuming.)
My question is, why bother derandomizing this way? Or even, why bother making the algorithm random in the first place?
It seems to me that an equally good algorithm would be the one-liner which deterministically sets all variables to 1. Given some MAX SAT instance as input, it seems to me that you would also expect this to (i.e., "in expectation it would") satisfy half of the clauses. To me, the analysis of the random algorithm really seems to say that any fixed guess is "good." (Rather than showing that our random algorithm is inherently good.) So why go through the process of randomizing and derandomizing in the first place?
Thanks in advance!


texts: What are these tree transformations called?

texts:
I want to transform a general rooted, node-labeled tree into a related binary tree. I came up with four different schemes ("left shallow", "right shallow", "left deep" and "right deep" binarization) that are illustrated by an example in the diagram below. They all preserve certain aspects of the original structure. Children stay children or become grand- (or grand-grand or grand*-)children. Also, new nodes are introduced (depicted in blue), which is fine for my application.

Does any of these four schemes have a name? Or is it documented or studied somewhere?

I am aware of one documented "binarization" scheme, which is called Knuth transform (also in the diagram). It is also possible to recover the original tree from this and you don't even have to introduce new nodes while building the binary tree. However, I am not interested in this, since it brings former siblings into parent-child-relation, which I can't have in my application.


texts: Proving that converting min-heaps to max-heaps requires time Ω(n)

texts:
Suppose I have a min-heap SH stored inside an array. I can perform the operations:

view-min(SH) in $O(1)$
extract-min(SH) in $O(\log n)$
insert(SH) in $O(\log n)$
is-empty(SH) in $O(1)$

If I want to build a max-heap BH from the first one, the naive algorithm I can implement is obviously

BH <- build-heap()
while not is-empty(SH) do             O(n)
    elem <- extract-min(SH)           -> O(logn)
    insert(BH, elem)                  -> O(logn)
done

whose complexity is obvously $O(n \log n)$ worst case. Is this the best algorithm or there is any algorithm whose complexity is lower? Yes

According to Wikipedia we can at least achieve $O(n)$. Without making any assumption about our array being an heap. Can we use this fact to achieve $O(\log n)$ complexity? No

It should be impossible, because we have to deal with any of the $n$ items at least one time. Does this prove that the conversion is $\Theta(n)$?


texts: Solving second-order ODEs with Taylor series approximation of second derivative and linear algebra

texts:
I was told about an algorithm to solve ODEs which I thought was very clever. I am sure its not something new. It works by discarding the $\mathcal{O}(h^2)$-term from the usual formula for computing the second derivative:

$$f''_i = \frac{f_{i-1} + f_{i+1} - 2f_{i}}{h^2} + \mathcal{O}(h^2), \qquad i = 0,1,2,\cdots,N$$

one can rewrite the equations for the derivatives for all $i$, as a set of linear equations, then use smart Gauss elimination from linear algebra to find expression for $f$ with exactly $5N$ floating point operations.

(1) Does this method already have a name?

(2) Should I be excited about this algorithm? Is this a particularly good method? Or are there other very different algorithms for solving ODEs which are much better?


texts: What does an admissible numbering of computable functions look like?

texts:
I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions.
Initially my take on such an enumeration was from the point of view of an enumeration of programs. For instance, we could enumerate all possible Turing machines using some set of rules (for instance, first the 1-state machines, then the 2-state machines, with some sort lexicographic order within each of the groups). Or alternatively, perhaps we could encode each program uniquely via some numbering system and then simply take them in increasing order.
These produce computable maps from $\mathbb{N}\to$ set of computable functions. But of course these are not bijections since multiple programs will compute the same function.
So my question is, for the purposes of something like Rice's theorem, how does one construct an admissible numbering of the computable functions?


texts: Algorithm to find the closest possible value among several combinations

texts:
I have the following problem and would like an orientation on which algorithms I can try to adapt to solve it in the best possible way.
SCENARIO
A company has a warehouse where it stores several products. A product can be stored in several packages, for example:

1 box with 10 units
1 box with 3 boxes of 10 units
1 box with 30 units
1 box with 5 boxes of 30 units

Eventually these products need to be dispatched for consumption in the company's stores. Each store makes its own request for products according to their needs.
However, such requests do not take into account the available packaging, ie the quantity requested may or may not coincide with the quantity of a particular packaging.
Example:

1 box with 8 lunits
2 boxes with 2 units
1 box with 4 units
1 box with 6 units

The store could request 13 units of product, and thus there would be no packaging combination that could total exactly 13 units.
However, there would be the following options to meet the store order:

1 box of 8 units and 1 box of 4 units (total: 12)

1 box of 8 units and 2 boxes of 2 units (total: 12)

1 box of 8 units and 1 box of 6 units (total: 14)

1 box of 8 units, 1 box of 4 units and 1 box of 2 units (total: 14)

In a scenario like this I need an algorithm that might find the packaging combination to be closer to the exact value.
In the real scenario, there are dozens of possible combinations, where I need to find 3 possible combinations:

The combination that meets the exact requested quantity (requested: 20, combination: 20)
The combination that gets as close as possible through a lower value than requested (requested: 20, closest combination: 18)
The combination that answers as close as possible through a value greater than requested (requested: 20, closest combination: 23)

Is there an algorithm already known that can fit well into this scenario where I can just adapt to my context?


texts: A general picture of formal verification in software

texts:
I'm trying to piece together a general picture of the state of formal software verification, and I'm having a good bit of trouble. For context, I come from mostly a math background. I'm quite familiar with the state of automated theorem provers and proof assistants with respect to their use to prove well formed mathematical statements (e.g. in Coq, Isabelle, Lean, etc.). What I'm having trouble understanding is what is going on with "formal methods" in practical CS applications.
I've found that companies such as Microsoft and AWS have used TLA+ as a "formal method" in their software development somewhat substantially. But when I started to read Wayne's Practical TLA+ book, I found that he considered a program to be formally checked if we just check say  a sorting algorithm on lists of length $<n$ with entries between 1 and $n$ for some fixed $n$, i.e. we are just checking finitely many cases and saying that therefore the algorithm should work in general. This doesn't seem particularly interesting; just an example of particularly rigorous unit testing. Notably it is not a formal proof of correctness.
On the other hand, I've seen murmurs about Isabelle and Coq being able to prove things about software just like they can prove mathematical theorems. Though when I look into the books which seem to promise this, e.g. Chlipala's Certified Programming with Dependent Types, I see a lot of abstract stuff that seems to vaguely relate to formally verifying programs, but no examples of taking a real program written in a language that has widespread use (e.g. C++, Python, Java, etc.) or even just pseudocode and "verifying it", whatever that means.
Can someone try to clear up my confusion?


texts: An example where the algorithm of Hopcroft and Karp performs poorly?

texts:
I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I came up with where solved on paper in almost constant number of rounds.

Other questions here in the community targeting this problem tackle the worst-case running time or the time-bound proven in the original paper.

This running time seems to be a bit too loose, especially because the maximum matching problem in general and in bipartite graphs lacks a conditional lower-bound on its running time and I couldn't find any tight lower-bound on the number of needed rounds. I couldn't find a bound on the number of needed operations in constrained models of computing either (For example binary decision tree or so).

On the other side, the $O(\sqrt n)$ bound on the number of rounds from the original paper has not been improved since was found in the 1973 except in the parameterized context and in special classes of graphs.

Any ideas/suggestions are much appreciated :)


texts: Prove that $S_2$ is closed under union and complement

texts:
I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that:

It is immediate from the definition that $S_2$ is closed under union and complement.

I think that my problem is due to the fact that $S_2$ is defined slightly differently in my assignment. Here's the definition I must work with:

$S_2$ is the complexity class of all languages $L$ for which there exists a polynomial bound verifier $V$ and a polynomial $p$ such that for all $x \in \{0,1\}^*$:
$x \in L \Rightarrow \exists y \in \{0,1\}^{p(|x|)}  \forall z \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$
$x \notin L \Rightarrow \exists z \in \{0,1\}^{p(|x|)}  \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=0$

Let's look first at union. Let $A,B \in S_2$. I thought of defining a new verifier $V_{A \cup B} = V_A \lor V_B$ which should return a correct answer. However, my problem is defining the new polynomial $p$. Let's say that the polynomials that exist for languages $A,B$ are $p_A,p_B$ and that $p_A < p_B$. Now let's look at some $x \in A \cup B$.
The problem is that if $x \in A$ all I know is that there exists a $y$ s.t. $|y|=p_A(|x|)$ and that if $x \in B$ there exists a $y$ s.t. $|y|=p_B(|x|)$. But how do I define a polynomial $q$ such that I can be sure that there exists a $y$ s.t. $|y|=q(|x|)$ for any general $x$?
As for the closure under complement, if $A \in S_2$, all I know is that if $x \in \overline A$, then $x \notin A$, therefore $\exists z \in \{0,1\}^{p(|x|)}  \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=0$. However I do not see how we use this in order to conclude that $\exists y \in \{0,1\}^{p(|x|)}  \forall z \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$.


texts: Do L-systems have a corresponding automata?

texts: So, I was reading about L-systems and it seems that L-systems are in many ways analogous to context-free grammars. Is there a corresponding automata for this? I can't seem to find anything on the Wikipedia page.


texts: I am quite new to python. I want to create a Python program to output the smallest palindromic number above a given input. But this input can be up to 20 digits. I tried finding all the palindromic numbers and adding them to a list. But it seems like for 20 digit numbers, it is a very long process. What python code would work? Secondly, I needed to find the largest difference between a palindromic number (of up to 20 digits) and then the next highest palindromic numbers. Finally, I had to find how many integers between 1 and 99999 are not the sum of 2 palindromic numbers. It seems to be a difficult task without storing all the palindromic numbers first.


texts: Is it possible to encode an arbitrary computation as a series of NP complete problem instances?

texts:
For example, can I make a compiler that transforms a C program (Turing complete language) into a bunch of SAT instances.

This encoding would be motivated as a way for specifying a problem piecemeal, where work on each piece could be verified in polynomial time.


texts: How much information, in bits, is conveyed by a 3-bit output representing how many 1s in a 7-bit input?

texts:
Let's say I have a combinational device that has an input of 7 bits and outputs a 3-bit binary number that reflects the number of 1s among the 7 bits.
How much information would be conveyed by the following outputs: 000 and 001?
I know information, in bits, is calculated by log2(1/p), and p is M/N, where N is the number of equally probable choices, and M is the amount of choices left after being given a piece of data.


texts: What kind of formal language is generated by Parsing Expression Grammars?

texts:
I've been unable to find what class of languages is recognized by PEGs. The original paper [1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also demonstrates how to construct a Top-Down Parsing Language grammar from PEG, but I've been unable to find what language is recognized by them either.

[1] Bryan Ford. Parsing Expression Grammars: A Recognition Based Syntactic Foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2004) http://www.brynosaurus.com/pub/lang/peg.pdf


texts:
Is the language consisting of the bitwise XOR of elements of two regular languages still a regular language?

For example, consider
$$L=\{ x \operatorname{xor} y \mid x \in A, y \in B, |x|=|y| \},$$
where $A$ and $B$ are both regular languages.

Can I say that $L$ is also a regular language?


texts: The number of samples in SUS selection method

texts: In stochastic Universal Sampling selection method of genetic algorithm, the number of selected samples is usually static. I wanted to know if it is possible to select  the number of these samples dynamically. For example, in the first iteration the distance between samples is 1/6 and in the next iteration this value changes to 1/7. Is it possible? If it is, what conditions or factors can determine the number of the distance between samples?


texts: Given complete graph, find optimal path with two costs on each edge

texts:
We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of both of the sums $a$ and $b$ of the edges laying on the edges crossed on the path.

One person told me that this is easily solvable by taking the maximum of $a \text { and } b$ for each edge and then using the dynamic programming technique storing the  final index and the bitmask of visited nodes. I couldn't find a counter test case, however I'm not sure if this is correct approach.


texts: How do I show that M1, M2 are two Turing machines such that L(M1) ⊆ L(M2)?

texts:
I am currently studying for a midterm tomorrow and my professor gave us links to backtests online. This is problem #3 in the following back quiz:

http://www.myoops.org/cocw/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-045JAutomata--Computability--and-ComplexitySpring2002/5C8B3587-B7B6-4D5B-A285-06F6551E9D27/0/quiz2.pdf

I am thinking that we need to construct a second turing machine to enumerate certain strings to prove the subsets, but I do not know where to start. I also cannot find a proof online anywhere that is similar to this. If someone can point me towards the right direction so that I can understand this concept, that would be great. Thanks!


texts: Efficiency of 0-1 linear programming w.r.t. number of binary variables

texts:
I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0.

Lets say I have a fixed number of $n$ variables in my program of which $k \leq n$ are binary. The other $n-k$ variables are continuous. My question is:
What can be said about the efficiency of solving these problems with respect to $k$? I know that 0-1-programming is NP-hard, but does it make a difference whether $k$ is small or large?

In my problem setting, I can somewhat modify the parameter $k$, i.e. the number of binary variables. Is it recommendable to lower them if possible ($k=0$ is impossible)? If so, why?

Thanks in advance

P.S.: If someone could point me to a paper discussing this, I'd happily download it.


texts:
Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}}$, where $z_{i} = x_{i}$ or $z_{i} = y_{i}$, no more than $n + 1$ times. So, for every request we set required $z_{i}$ (that is, $x_{i}$ or $y_{i}$) for every $i$.

Moreover, we have $n$ bits of unwritable memory, namely, every bit of that memory is set once and then does not change. This memory is avaliable all the time, but requested $Z$ strings drop out before the next request, so, we don't have complete list of all requested $Z$ strings.

The problem is to check if $X = Y$ with given $n$ bits and $n + 1$ times for $Z$ string request.

There is an extra question: is it possible to use $\mathcal{O}(\log^{2}(n))$ bits of memory and $\mathcal{O}(\log(r))$ requests.

I don't really understand area of CS that is closely related to the problem, could anyone give a hint?


texts: Is there an algorithm to find the minimal number of dimensions, given the distances between points?

texts:
Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$

where $\Vert \cdot \Vert$ is the euclidean norm.

Is there an algorithm to determine the minimal $m$ just from $D$ such that there are $\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$ with $d(i,j) = \Vert{y_i -y_j}\Vert$?

Or equivalently: Given $D$ as well as some $m$, can we determine whether $D$ can stem from $k$ points in $\mathbb R^m$?


texts: How to solve T(n)=2T(√n)+log n with the master theorem?

texts: I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?


texts: Special term for a cycle containing a single vertex and edge

texts: Is there a special term for a cycle containing a single vertex and edge?  I feel like I read "self-cycle" somewhere, but can't find where.


texts:
This problem involves the time-complexity of determining set intersections, and the  algorithm must give output on all possible inputs (as described below).

Problem 1:  The input  is a positive integer $m$, and two  unordered subsets $A$ and $B$ of $\{1,\dots,n\}$. The size of the input is $n+ |A| +|B|$.

Output: The set $A \cap B$, the intersection of $A$ and $B$.

As all  infinitely many  possibilities  are ranged through,  with  the size of output $n = m + |A| + |B|$,   is there a linear-time  algorithm that on any $(n,A,B)$, outputs  $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Problem 2:  The input  is a positive integer $m$, and  $j$ unordered subsets $A_1, \dots, A_j$  of $\{1,\dots,n\}$. The size of the input is $n+ |A_1| + \cdots + |A_n|$.

Output: $A_1 \cap  A_2 \cap \cdots \cap A_n$, the intersection of $A_1, \dots, A_j$.

As all infinitely many  possibilities  are ranged through,  with  the size of output $n = m + |A| + |B|$,   is there a linear-time  algorithm that on any $(n,A,B)$, outputs  $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients?  (Worst-case complexity.)

Are there references to the time complexity of these problems? I’m interested in the particular algorithms themselves, but if anyone knows that complexities above are linear-time or $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients, I’d be grateful to hear from you.  ( I’m less interested in algorithms that involve hash functions, but as long as such an algorithm works on all possible inputs, a hash function algorithm is okay.)   I’m not a computer scientist student but an older person learning things as they come along in work-in-progress.


texts: why is the max number of Nodes mod(N/m) + mod(N/m^2) + 1 in R-tree?

texts:
I am going through Antonin Guttman's paper on R-tree. It mentions the max no of nodes given N index records in an R-tree is |N/m| + |N/m^2| + 1.

If there are N index records and if we choose to have minimum number of entries (m) in each node, wouldn't we just need N/m nodes at max? Why do we also have N/m^2 + 1?

Here's a link to the paper


texts: How to read out a double negation in propositional logic

texts:
How would one verbally say ~~R where R = my program is correct? The tildes are negation symbols. I'm not sure if it just cancels out and comes out as 'my program is correct' or if it's something else.

Thank you!


texts: Index matching algorithm without hash-based data structures?

texts:
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.

Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.

For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.

Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.

So my question is whether there is a linear algorithm for this task that does not use any hashsets.


texts:
I am working on an implementation of inverse kinematics using the jacobian transpose method. The implementation seems to be working as it does find the "theta" vector, although sometimes it might take an insane amount of steps to do so, which makes me believe that it is not correctly implemented.

So after reading a bit on it, it appears as if each step is guaranteed to be closer to the end effector than the previous step. Is this a correct assumption?

In my implementation it is not always closer for every step, so it might be a decent indication that there is something wrong


texts: How to find the square with the highest total sum

texts:
I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most.

For example if n = 3. I have a matrix of size 12 x 12. In the below picture, you can clearly see that n^2 square (outlined in red) adds up to the most. For simplicities sake, I made all the numbers 5, expect for 9 of the boxes which are 9999 so its clear that that is the n^2 squares that add up to the most.

My approach to solving this problem was to essentially create a n^2 square and brute force the entire 4n x 4n matrix. However, that runs in O(n^4) time complexity. How can I do it in O(n^2)?


texts: Is it possible to repeat a wildcard in regex?

texts:
.{5} would match any string of 5 symbols (excluding newline). Suppose I wanted to define "a 5-character repetition of a single character."

The immediate way that comes to mind is (.)\1{4}, but this relies on a back reference.

Using a subset of regex which is dependent only on |,(),*,concat any regex expression of pattern size M and search string size N can be solved with a  means an M-size NFA in O(NM) time.

Backreferences, unlike +, {n}, etc. are not derivable from the restricted regex tools above, and result in exponential times.

Is it possible to replicate the desired pattern in the non-exponential-time subset of regex (without using exponential* size)? If not, then why (how can we prove so)?

*one could go factorial in size by brute-forcing in this case.


texts: Level sums, displacements: how to determine their effect efficiently?

texts:
Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$,
$\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.

Define $$S(\delta,m) = \sum_{n\in R: \rho(n)\geq \delta} f(n+m).$$

Is it possible to compute $S(\delta,m)$ efficiently? To be precise: say we are given $\delta_i\in \lbrack 0,1\rbrack$, $m_i\in R$ for $1\leq i\leq N$. Is it possible to compute $S(\delta_i,m_i)$ for all $1\leq i\leq N$ in roughly linear time on $N$ (or some other time substantially smaller than $N^2$)?

To see why this might not be an unreasonable request, consider the two following extreme cases.

If all $m_i=0$ (or all $m_i$ are equal), we can compute the $N$ sums $S(\delta_i,m_i)$ easily in linear time.

If all $\delta_i=0$ (or all $\delta_i$ are equal), we can compute the $N$
sums $S(\delta_i,m_i)$ in roughly linear time (more precisely: $O(N \log N)$) using FFT. The reason is that $S(\delta,m_i)$ equals $F(m_i)$, where $F$ is the convolution of $f$ with the function $g(n) = \begin{cases} 1 &\text{if $\rho(-m)>\delta$,}\\ 0 &\text{otherwise.}\end{cases}$.

Is the general problem feasible? Can it be shown not to be feasible?


texts: Interpreting algorithm time complexity analysis

texts:
Lets say we have the following loop and want to find its time complexity:

0: def example_loop(n):
1:     i = 0
2:     while i < n:
3:         print(i)
4:         i = i + 1

One possible approach is to first determine that for each individual row it's $\Theta (1)$ (row 4 is $\Theta (1) + \Theta (1) = \Theta (1)$). Thus, the complexity of the loop's body is $\Theta (1) + \Theta (1) = \Theta (1)$. The second line of the code is executed $n + 1$ times while lines 3-4 are executed $n$ times so for the lines 2-4 we get $(n + 1) \cdot \Theta (1) + n \cdot \Theta (1) = \Theta (n) + \Theta (1) + \Theta (n) = \Theta (n)$. Adding the lines 0-1 the result becomes $\Theta (1) + \Theta (1) + \Theta (n) = \Theta (n)$.

However, my study materials offer an alternative approach without an explanation which I don't really understand. In it, all individual lines are still $\Theta (1)$. Similar to the first approach, the lines 3-4 together are also $\Theta (1)$, but after that the solution replaces the $\Theta (1)$ of line 2 with $[A_1; B_1] \cdot 1$ and the complexity of lines 3-4 with $[A_2; B_2] \cdot 1$. From that $[A_1; B_1] \cdot (1 + 1 + 1 + ...) + [A_2; B_2] \cdot (1 + 1 + 1 + ...) = [A_1; B_1] \cdot \Theta (n) + [A_2; B_2] \cdot \Theta (n) = \Theta (n) + \Theta (n) = \Theta (n)$ and after this, the solution proceeds like the first one where we add the first two lines to the rest and get $\Theta (n)$. I have no problem following before the replacement, but I'm hoping for an explanation where exactly do $[A_1; B_1] \cdot 1$ and $[A_2; B_2] \cdot 1$ come from and what is the difference between this and the first approach?


texts: Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL

texts:
I am trying to prove that the language $L=${$0^n 1^m |m ≤n^2$} is not a context free language. To do so I selected a string $w=0^p 1^{p^2}$. However, I am new to the CFL pumping lemma, and I am not sure if my proof is correct. Specifically, does the value of $i$ need to be the same for all divisions?

My first division is: v and y both contain 0’s.

$u=0^h$

$v=0^j$

$x=0^k$

$y=0^q$

$z=0^{-h-j-k-q} 1^{p^2}$

When $i=0$, I get $uv^0 xy^0 z=0^h 0^0j 0^k 0^0q 0^{p-h-j-k-q} 1^{p^2}=0^{p-j-q} 1^{p^2}$. This means $w$ contains less than p 0’s, but p2 1’s. This means for any valid value of p, there are more than p2 0’s. So this is not in the language.

The second division is either v or y contain both 0’s and 1’s. When $i=2$ I have $v=0^j 1^k$ or $y=0^j 1^k$, when $i=2$, so 0’s and 1’s out of order as the sequence $0^j 1^k$ will be repeated.

Finally the case that both v and y contain 1’s.

$u=0^p$

$v=1^j$

$x=1^k$

$y=1^q$

$z=1^{p^2-j-k-q}$

When $i=3$, the string becomes $uv^3 xy^3 z=0^p 1^3j 1^k 1^3q 1^{p^2-j-k-q}=0^p 1^{p^2+2j+2q}$.
This means s contains more than $p^2$ 1’s, but only p 0’s, so the string is not in the language.


texts: Who was the first to define the RAM model?

texts:
I am working on a project where I refer to the RAM model, I explain what it is, but I am not sure who defined it first.

The wikipedia article is not very explicit about it, and the first citation is from 1946.

Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.


texts: Finding the longest path of sum $0$ in a weighted tree

texts:
How to find the longest path with the sum $0$ in a weighted tree (where each edge is labeled with an integer weight)?

In other words, I want to find a path so that the sum (sum of numbers on edges) is equal to zero, and the amount of edges along which I went is the maximum.


texts: Algorithm to create a set of distinct numbers and a bag of numbers so that each number in the bag is also contained in the set

texts:
I am looking for a simple algorithm that creates a set and a bag of numbers so that all numbers in the bag are also contained in the set.
Additionally, the numbers should be created in pseudo-random order.
For example, the numbers for the set could be created like so:
7, 2, 3, 9, 4, 6, 1

And the numbers for the bag maybe like so
3, 1, 9, 9, 3, 2, 1, 2, 7, 3, 2, 4, 6, 9, 1, 2, 9, 3

When starting the algorithm, I'd like to specify the number of numbers in the set and some sort of distribution for the numbers in the bag (say: 50% of numbers occur 4 times, 25 % of numbers occur 3 times etc.). Ideally, the numbers are integers, but this is not a requirement.
Unfortunately, I am lacking the proper vocabulary for this kind of requirement, but I hope that this description gives an approximate picture of what I am after.
Is there such an algorithm, or what are the search terms to find such algorithms?
Clarification
As per D.W.'s comment: the input would be: a number n that specifies the desired number of numbers in the set, and a vector of pairs of integers (a1, o1), (a2, o2)...(ax, ox) with the following property: sum over ai is equal to n and ai numbers of the set occur oi times in the bag.
For example, n = 5 and vetcor = (3,2), (1,1), (1,0).
First I need five (n) random and distinct numbers, for example
 4, 9, 7, 5, 6

Then: 3 of the numbers should occur twice (3,2) in the bag, one number once (1,1) and one number should not occur at all (1,0), for example
 9, 4, 4, 6, 5, 9, 5

(9, 4 and 5 occur twice, 5 occurs once, 7 does not occur at all).


texts: find the shortest path between two nodes where the number of edges is minimal

texts:
Say you are given an undirected unweighted graph, where s and t are nodes from the graph.
d(s,t) means the distance between s and t which outputs the number of edges.

How do I find the the maximum distance between s and t ,
max{d(s,t)}, where the edges between s and t are minimal?
Also, how can this problem can be related/reduced to the hamiltonian problem?

Any advice would be really helpful.


texts: Time complexity of mutually recursive functions

texts:
Suppose I have two mutually recursive functions like this:

f1(x)
{
   .//some code
   .
   .
   f1(x-1)+g1(x-1);

}

g1(y)
{
   .
   .//some code
   g1(y-1)+f1(y-1);
  ..

}

How can I calculate time complexities in such cases?


texts: Underlying language to specify various types of logic

texts:
There exist several different types of logic -- 1st order, 2nd and higher order with many different sets of inference rules possible.

What I'm having trouble understanding is what's the "underlying logic" we use to talk about the various different types of logic. For instance, if we were limited to thinking in terms of $i$th order logic, then we couldn't talk about $>i$th order logics but we can. Does this mean that the logic we think in terms of is more powerful than any $n$th order logic?

Sorry this is so vague but I'm having a hard time formulating my question exactly.

Edit: Turing machines cannot even decide all statements in first-order logic -- so does this imply some sort of relation between first-order logic and any other logic that we can think of (as humans are no more powerful than TMs)?


texts: Routing a DAG through 5 consecutive butterfly networks

texts:
I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that

  Using standard packet-routing techniques [Lei92], we can find switching actions for each node that establish collision-free paths in the graph for each packet.

The goal is to emulate a circuit (containing $m$ (arity 1 and 2 only ?) gates and $n$ inputs) using 5 consecutive copies of the butterly network of order $r$ (where $2^r\geq n+m$).

First question

Where do I find the quoted result in [Lei92] ?

I am unable to locate the relevant result in Introduction to parallel Algorithms and Architectures, F.T. Leighton. I didn't find anything on the internet either when looking for "embedding directed acyclic graphs in butterfly networks" for instance. I found many interesting results about routing permutations, and there is a whole section that talks about packet routing, but I can't find what the authors quote...

In the following paragraph, the authors discuss the labels one may put on nodes. In particular they write that there are

  4 switches (depending on how you count them)

It would seem most natural to me to have

the empty switch : we won't be routing anything through here
two "single wire going straight ahead" kind of switches
two "single wire making a switch" kind of switches
two fan-out switches
one "two wires coming in and going straight ahead" kind of swich
one "two wires coming in and making a switch" kind of switch

for a total of 9 ``natural'' switch types for intermediate nodes in the router. I can see that the 9 switches I describe can be clustered in 4 categories

empty (only 1 of this kind)
1-1 (single wire in, single wire out : 4 of this kind),
1-2 (fan out : 2 of this kind),
2-2 (two wires in, two wires out : 2 of this kind)

Second question

Why would the authors only talk of 4 switches ? Is this somehow more natural than ?


texts:
How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree?

I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ leaves by the Fibonacci sequence and didn't know how to continue!

Could somebody help?


texts:
Computer Language/Logic Examples?
These are some of the questions i am having within a few chapters of my automata class and would like some help if you could :) Class is online and can be hard to self teach at times, you dont have to answer all or any for that matter, just thought id ask i got a midterm coming up and would like to know how to do these. ¯(ツ)/

Λ is not a word but it’s still used in its language? How do I show that there are other CFGs for these languages that do not use Λ-productions.

(ex i) S → aX | bX
 X → a | b | Λ

(ex ii) S → aX | bS | a | b
 X → aX | a | Λ

(ex iii) S → aS | bX
 X → aX | Λ

(ex iv) S → XaX | bX
 X → XaX | XbX | Λ

How would I convert these CFGs to CNF?
 (ex i) S → SS | a

(ex ii) S → aSa | SSa | a

(ex iii) S → aXX
 X → aS | bS | a

(ex iv) E → E + E
 E → E * E
 E → (E)
 E → 7
 The terminals are + * ( ) 7

How would I make a PDA that accepts the same language (given that a CFG makes L then a PDA makes L)
 S → XaaX
 X → aX | bX | Λ


texts:
Given a language $L\subseteq \Sigma^*$ in $P$, is the language

$subwords(L) = \{v\in\Sigma^* : \text{there exist } u,w\in \Sigma^* \text{ with } uvw\in L\}$

that consists of all subwords of words in $L$ also guaranteed to lie in $P$?


texts: How does the midpoint line drawing algorithm work?

texts:
I'm having trouble understanding the mechanics of the midpoint algorithm. I understand the gist of what it does; it keeps us within a half a pixel of where the actual line should be printed. It does this by updating this $d$ value for each pixel that we traverse.

However, even after drawing some samples and observing what the $d$ value does, I can't figure out the true inner workings of it, and how updating it by these $\Delta_e$ and $\Delta_{ne}$ symbols (which are also a bit of a mystery to me) keeps our pixel placement in check.

Can someone summarize it in simple terms for the good of all humanity?

The Algorithm:

Line (x1, y1, x2, y2)
    begin
    int x, y, dx, dy, d, deltaE, deltaNE;
    x <- x1;        y  <- y1;
    dx <- x2 - x1;  dy <- y2 - y1;
    d <- 2*dy - dx;
    deltaE <- 2*dy;     deltaNE <- 2*(dy - dx);

    PlotPixel(x, y);
    while ( x < x2) do
        if (d < 0) then
        begin
            d <- d + deltaE;
            x <- x + 1;
        end;
        else begin
            d <- d + deltaNE;
            x <- x + 1;
            y <- y + 1;
        end;
        PlotPixel (x, y);
    end;
end;


texts: How to traverse on only a cycle in a graph?

texts:
I'm attempting ch23 in CLRS on MSTs, here's a question:

  Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges not in T . Give an algorithm for finding the minimum spanning tree in the modified graph.

A solution I found was to add this new changed edge in T, then exactly one simple cycle is created in T, traverse this cycle and delete the max-weight edge in this cycle, voila, the new updated MST is found!

My question is, how do I only traverse nodes on this simple-cycle? Since DFS/BFS traversals might go out of the cycle if I, say, start the traversal in T from one endpoint of this newly added edge in T.

One solution I could think of was to find the biconnected components in T after adding the new edge. Only one BCC will be found, which is this newly formed simple-cycle, then I can put in a special condition in my DFS code saying to only traverse edges/nodes in this BCC, and once a back-edge is found, stop the traversal.

Edit: graph G is connected and undirected btw


texts:
I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that:

HeapSort: A procedure which sorts an array in place.

Build-Max-Heap: A procedure which runs in linear time, produces a max- heap from an unordered input array.

Is worst-case input = worst-case running time?

If so, given the size n for Build-Max-Heap, would its worst case input be the same as the HeapSort which is $\mathcal{O}(n \log n)$?


texts: What is the constant $C$ in the definition of asymptotic notations?

texts:
For example in the definition of $\Theta$:

  $f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that
  $$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for all } n \geq n_0. $$

I was scratching my head for two weeks since we took this definition in class. Why do we need this constant anyways? Shouldn't we get rid of all constants because they aren't significant?

Why can't we just say $g(n) \leq f(n) \leq g(n)$?


texts:
I am working on the following exercise:

Consider an undirected graph $G = (V,E)$. Let $T^* = (V,E_{T^*})$ be a $MST$ and let $e$ be an edge in $E_{T^*}$. We define the set of all values that can be assigned to $w_e$ such that $T^*$ remains a MST as $I_e$.

Show that $I_e$ is an interval.
Devise an efficient algorithm to calculate $I_e$ for a given edge $e$.
Devise an efficient algorithm that determines all $I_e$ in one step. It should be more efficient than repeatedly using the algorithm from 2.

I did the following:

Consider an edge $e$ in $E_{T^*}$. Delete it from $G$ and find the new lowest weighted edge connecting the resulting components, say $e'$. The upper bound for $I_e$ is $w(e')$. The lower bound would be $-\infty$.
Use the algorithm sketched in 1.
I do not know what to do here. Could you help me?


texts: Clique in P when the input graph's connected components have at most $3\log|V|$ vertices?

texts: What's the time complexity of the clique problem for input graphs where each connected component has size at most $3\log|V|$? Is it in P?


texts:
Let be $B$ a Busy Beaver function and set $W=\{\langle M \rangle :\text{$M$ stops in less than $B(10^{1000})$ steps on an empty tape}\}$. Is this set computable?

I'm not sure how to approach this question. I suspect that this set is computable and have tried to see if it is finite, but haven't reached anything.


texts:
What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many times we want on every vertices and/or edges. Let's say, on my graph, that I want the minimum distance for visiting every blue node. What algorithm and heuristic would you recommand me? An approximation running in reasonable time would be acceptable.

For this example, this is an undirected graph, the vertices are points in the plane and the cost of an edge is the distance between its endpoints.


texts: Are there any non-naive parallel sparse matrix multiplication algorithms?

texts:
I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on algorithms for multiplying sparse matrices.

However, all I found so far were different ways of arranging the more or less naive "outer product" algorithm between processors - the same total number of multiplications/additions with different amounts of communication and additional algorithmic overhead (which, though, is undoubtedly important).

The most non-trivial algorithm I found was the Yuster-Zwick algorithm described in Fast sparse matrix multiplication, which is basically a combination of the same old naive algorithm and using a fast dense method for the dense part of the problem.

I looked at how sparse matrix multiplication is implemented in MLLib and it, too, appears to use the simple block-based algorithm.

Are there any parallel algorithms for multiplying sparse matrices that are substantially different from the naive one - as different as Strassen's or Coppersmith-Winograd's algorithms are from the naive algorithm for multiplying dense matrices?

For concreteness, let us assume that the matrices are sparse enough that number of non-zeros in the arguments and in the result are both $O(N)$.


texts: Is paging the division of processes and segmentation the division of main memory?

texts: This is what I know thus far, logical address space is the processes and physical address space is the memory. If paging is the division of logical address space and segmentation the division of physical why is it said that pages are physical divisions and segments are logical divisions? I assume something is wrong here, not sure what.


texts: How to show that given language is unambiguous

texts:
Given following grammar:

$$
\begin{align}
S \rightarrow &A1B \\
A \rightarrow & 0A \mid \varepsilon \\
B \rightarrow & 0B \mid 1B \mid \varepsilon \\
\end{align}
$$

How can I show that this grammar is unambiguous? I need to find a grammar for the same language that is ambiguous, and demonstrate it.

I know if I was asked to prove that the language is ambigious then I should find two different parse trees for same string, but I don't know what to do.


texts: algorithms, number of instructions in the code

texts:
How many instructions as a function of the input size N?

int count=0;
for (int i=0; i<N; i++)
  for(int j=i+1; j<N; j++)
    if(a[i] + a[j] ==0)
       count++;

# of "less than" compare instructions  = 1/2(N+1)(N+2)   Can someone pl. explain why there is 1/2 multiplier?

# of "equal to" compare instructions = 1/2 * N * (N-1).
The same here why is there 1/2 * (N-1). Shouldn't it be just N?

also when do we increment j++?, after count++ or after we increment i?

Thank you!


texts:
I want to generate a completely random Sudoku.

Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a unique way to complete it to match the Sudoku constraints (each line, column and aligned $3\times3$ square has no repeated element) and it is minimal in that respect (i.e. if you omit any more element the puzzle has multiple solutions).

How can I generate a random Sudoku puzzle, such that all Sudoku puzzles are equiprobable?


texts: Dynamic path planning and waypoint sorting

texts:
Good evening everyone,

I have a question that I am having a bit of trouble formulating properly and thus it is making it complicated to look up literature on the subject. What I am looking for is a name for a more general problem of the same nature, and I think it will have something to do with the title of this question, dynamic path planning and sorting.

Before getting into the details, I'll try to summarize the question as best as I possibly can:

Attempted Summary

In a complete and weighted graph, which algorithm(s) should be used to continuously obtain a path which maximizes the reward obtained from visiting vertices if the rewards are dynamic and thus constantly changing?

And now, a bit more context.

Problem Statement

Suppose we have a robot:

The robot is capable of autonomous movement
It is fitted with several sensors
The robot must patrol a set of locations L and gather data using its sensors at all of the li ∈ L
Some locations are more interesting than others, and may be worth visiting more frequently. What makes these locations "more interesting" is that data taken from these locations have a higher variance than the data taken from other locations. Also, it is important to take into account the time since the location was last visited. The longer it has been, the more desirable it will become to visit.

The goal is to properly schedule the order in which the different locations should be visited so that we can both maximize the information gain and minimize the energy expended by the robot, e.g: the distance traveled. We can assume the robot can move freely from any point and to any location, not just from location to location. Also, the robot must gather data continuously for a period of time T, so the scheduling has to be done more than once.

My view

To me, it looks like this problem can be modeled as a graph. The vertices represent each of the locations that the robot must visit, and the edges have a cost associated to them which represent the distance that must be traveled. I believe the robot itself can also be modeled as a vertex in this graph, which has edges connecting it to every single other location. We can assume all locations are also fully connected between each other, since the robot can go from li to lj such that ∀ i, j ∈ L, however some of these pairs will not be desirable given the distance.

So we are trying to minimize energy expenditure while maximizing information gain. This part sounds like an optimization problem. If I can model the information gain or "reward" obtained from visiting each vertex, taking into account factors such as arbitrary importance of the vertex and variance, it might make sense to use a classical pathfinding algorithm, however I am not too sure how these algorithms behave when used against vertices whose rewards change over time (the overall reward of a vertex will be affected by the amount of time that has passed since it was last visited).

I have also thought about modeling this as a linear programming problem, however I am not quite sure how to obtain a sorted set using this approach (of course I can get the best and worst locations to visit, but what about the order of the rest?)

Thank you for your suggestions.


texts: Do closure properties for languages go the other way?

texts: For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?


texts: Is Universality Theorem applicable to Halting problem?

texts:
This is Universality theorem In the Computability, Complexity and Languages book written by Davis in page 70:

If $\phi^{(n)}(x_1,...,x_n,y) = \psi_P(x_1,...,x_n)$        $where$  #$(P) = y$
Theorem 3.1 (Universality Theorem): for each $n>0$ the function $\phi^{(n)}(x_1,...,x_n,y)$ is partially computable.

From what I understand of this theorem, the universal program is more like an interpreter it takes $x_1,...,x_n$ as input and $y$ as a program number and simulates what program with number $y$ does on the $x_i$s.
Since there is no program for halting problem so there is no $y$ for it to be passed to $\phi^{(n)}(x_1,...,x_n,y)$ so I think this theorem is not applicable to halting problem.Is it right?


texts:
I am currently writing from a computer on which a VM has just frozen due to exhausted RAM. I am obviously no expert in the field of operating systems but i know that they implement certain memory management methods so why can't my OS handle my alt-f4 request to kill the troublesome process in a reasonable time?

Why can't other processess still run normally?

Shouldn't operating system swap between active tasks so that my keyboard input reaches said process?

Operating system in itself should be of top priority with handling user input isn't that right?

Therefore my question remains: how come, despite all the round-robin and/or other scheduling mechanics my OS still freezes?

Thank You for all the answers.
Cheers.


texts: Is the punctuation part of the alphabet?

texts: Given a language $L \subseteq \Sigma^*$, (it could be Italian, English, C++ or anything else), should we consider the punctuation (".", ";", "->") as a part of the alphabet $\Sigma$ upon the language is built on or not?


texts: How can the VC-dimension of Turing machine be finite?

texts:
The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$  cannot shutter. This paper shows that the VC-dimension of the set of all Turing Machines with $n$ states is $\Theta(n \log n)$.

However, suppose that we take the set of all such Turing machines, for $n$ sufficiently large so that the universal Turing machine is a member of $\mathcal{H}$. The result states that there exists a set $C$ (wlog, $C \subset \{0,1\}^*$) of size, say, $n^2$, such that $\mathcal{H}$ cannot shatter. To my understanding, it means that there exists a function $f : C \rightarrow \{0,1\}$ ("labeling"), such that for every $h \in \mathcal{H}$, it holds that $h \neq f$. Since the elements of $\mathcal{H}$ are Turing machines, I say that "$h$ computes $f$" when the machine $h$ implements $f$.

But $C$ is finite hence $f$ is clearly computable, thus there is some Turing machine $M_C$ which computes it, therefore $M_C$ can be simulated by the universal Turing machine, which is in $\mathcal{H}$, and this is a contradiction (since we assumed $\forall h \in \mathcal{H}, f \neq h$ ). Where is the problem with this argument?


texts: Term rewrite system is non-confluent, but cannot find different normal forms of term

texts:
I wrote a simple TRS that I believe is non-confluent, but I'm not able to find a term with two normal forms for it.

The TRS is defined on the signature $\mathcal F=\{f,\ l,\ s,\ o\}$ and the rewrite rules $\mathcal R$ are defined as follows:

$l\to s(o)$
$t(x,\ l)\to s(x)$
$t(l,\ x)\to s(x)$.

This TRS is clearly finite and terminating.

For the first two rules, we have a critical pair $(t(x,\ s(o)),\ s(x))$ which is not joinable. Therefore, the TRS is not confluent.

It seems that for such a simple example I should be able to find a term with two normal forms. What am I missing?


texts:
I have to come up with a proof of correctness of the following algorithm: GuardedSearch(A; v)

Input: an array A of n numbers and a number v

Output: an index i such that A[i] = v, or NotFound if no such index exists

i ← n
while i ≥1 and A[i] ≠ v
a. do i ←i−1
if i<1
a.  then return NotFound
b.else return i

I know that I have to come up with a loop invariant but I'm struggling to find a correct one. My main problem is with the fact that the while loop has two conditions and i don't know how to solve this. The one that I came up with is the following: At the start of each iteration, if V is not present in A, V is not present in the subarray A[i+1....n].

With this loop invariant, initialization is easy since there is an empty array and the loop invariant thus holds. However when going to the maintenance step I don't know how to continue. I think this is because my loop invariant is incomplete but I have no idea how to get to a correct one. Could anyone help me?


texts:
While reading an article, I noticed the use of term 'I/O Task':

Indeed, suppose the currently running process is performing an I/O
task (which, by definition, does not need the CPU to be accomplished).
Then, the OS may interrupt that process and give the control to one of
the other in-main-memory programs that are ready to execute (i.e.
process context switching).

However, AFAIK a unit of execution (task definition) is either a thread or a process.
So what does an "I/O Task" mean?


texts:
I'm trying to use the pumping lemma proof to show that the following language is context-free rather than regular

  $\{ba^n bc^n | n \geq 1\}$

I've been looking at tutorials on Youtube to try and gain an understanding but as of yet I cannot get my head around it.

Is someone able to take my example and show step by step how to solve using the lemma.

Thanks in advance,


texts: Kernelization trick, for neural networks

texts:
I've been learning about neural networks and SVMs.  The tutorials I've read have emphasized how important kernelization is, for SVMs.  Without a kernel function, SVMs are just a linear classifier.  With kernelization, SVMs can also incorporate non-linear features, which makes them a more powerful classifier.

It looks to me like one could also apply kernelization to neural networks, but none of the tutorials on neural networks I've seen have mentioned this.  Do people commonly use the kernel trick with neural networks?  I presume someone must have experimented with it to see if it makes a big difference.  Does kernelization help neural networks as much as it helps SVMs?  Why or why not?

(I can imagine several ways to incorporate the kernel trick into neural networks.  One way would be to use a suitable kernel function to preprocess the input, a vector in $\mathbb{R}^n$, into a higher-dimensional input, a vector in $\mathbb{R}^{m}$ for $m\ge n$.  For multiple-layer neural nets, another alternative would be to apply a kernel function at each level of the neural network.)


texts:
Suppose a processor lacks STACK Pointer Register. But, It does have STACK.
Then, in my opinion, a program will still be able to call subroutines but, will be unable to return back from the subroutines.
Please do clarify me where I have made a wrong assumption.
Also do mention the possible outcomes of the scenario.


texts: What is an example for a decidable language not in P?

texts: I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there  a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?


texts: Hash function for searching, is that feasible?

texts: I have a set of sorted values $\left\{a_j \right\}_{1 \leq j \leq n}$, suppose now a number $x$ is given and we would like to find out the index $j$ such that $a_j \leq x < a_{j+1}$ (you can assume always $- a_1 =  a_n = +\infty$). I could find such index with a binary search on the lower bound (which would take $O(\log n)$). However I wonder if a search using some kind of hash function could be used to speed up the search, I think is a kind of similar problem, if not the same.


texts:
Problem:

  We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable.

My attempt:

A set is countable if it is finite or there is a one-to-one correspondence with the natural numbers. So we need to show that a strategy for an enumeration exists. I'm not sure exactly how detailed I'm supposed to be here, but I just tried to give a general way in which one could enumerate the set of binary trees as defined above...

Assign the first k_0 positive integers for each binary tree with height 0, then assign the next positive integers for each binary tree having height 1, and so on. The set of all binary trees can be enumerated this way and is thus countable.

Is the above the right way to go about this problem? (I'm not sure if I'm supposed to provide a specific function for how many binary trees there are at any given height k.) Thanks.


texts:
I have no idea how I managed to get this far in life without ever really grasping this but as it happens I'm still very confused on the concept of a hash function. I did some googling/wikipedia-ing, and here's what I get:

hash tables are nice because the index can be stored in a smaller array
hash functions are kind of like uniform random number generators that always have the same seed but not really (and I don't get why)

But here are the parts that are still very ambiguous to me:

Why use a hash function and not an RNG with a set seed and array size?
Why is it ok to have "collisions", which from what I understand is two keys pointing to the same index? I mean don't we rely on that stuff to be reliable?
Why do we mod with array size at the end? Can't we just restrict the range of the hash function?
what is the difference between a hash table and a pointer?
If we know the number of unique keys, why not just use direct addressing? What is so great about this uniform distribution of keys?
in the case that the number of unique keys are not known, exactly how is that calculated in the end? It seems like something really clever is supposed to happen here but short of just counting the number of entries in the table (and somehow accounting for collisions) I don't quite see it. Also, shouldn't we count the number of unique keys before even writing the hash function, since we have to determine the array size?

Thanks for any insight!


texts: Minimum-cut with minimum number of edges

texts:
I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.

Firstly, let's state (for completeness) that an s-t cut is the partitioning of the vertices in the graph, into two parts, such that the source s is in one partition and the sink t is in the other. The cut-set is the set of edges that are going from vertices in the partition that contains s to those in the other partition.

There may be multiple s-t cuts that have the same capacity as the min-cut (with different sized cut sets). The problem that I wish to solve is, how to find the minimum s-t cut that also has the minimum size cut set?

For example, in the following graph where s = 0 and t = 4:

We can clearly see that the capacity of the minimum cut is 2. One possible way to  get this is to take edges 0-2 and 1-3 (This cut set has size 2). Another possible way to do this is to take edge 3-4 instead (This cut set has size 1) which is the optimal answer.

I have researched about this question and some people are saying that we need to transform the edge capacity, C, of every edge to C * (|E| + 1)  - 1, where |E| is the number of edges in the graph.

One such discussion here: https://codeforces.com/blog/entry/51748
Another such discussion here: https://stackoverflow.com/questions/38408852/finding-the-lowest-amount-of-edges-in-all-minimum-cuts-in-flow-network

The problem is, I don't understand why this formula works. In particular, why do we need to multiply by (|E| + 1) and not some other number? I cannot see how multiplying by any other number would "change" the augmenting paths in the graph as stated in the cited links.

Could someone please advise me?

Edit: The offset in the formula should be +1 and not -1 in order to get the cut-set of the smallest size.


texts:
I'm just reading a textbook in mathematical logic, as following:

What is the precedence to consider the equality and satisfiability operators in the equation pinpointed in red?! In other words, which of following cases right:

(A \sat x) = y[s] or A \sat (x = y[s])


texts: Best way to learn Machine Learning after having done a Computer Science Bachelor

texts:
I just graduated from my university with a Computer Science Bachelor.

Because of this, I have good Python knowledge, coded a reinforcement learning AI, did machine learning ABCs with Iris flower detection and figuring out digits from the MNIST dataset using ANNs and CNNs, but that's the extent of my knowledge with respect to machine learning. I also have a decent background with linear algebra.

Given my position, what would you say is the best way for me to study Machine Learning? Self study? If so, could you recommend some resources?

Thanks!!


texts:
Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 = 9 values = 4 bits) for a total of 81x4x3 = 972 bits. By numbering each square, one can reduce the positional information to 7 bits, dropping a bit for each square and a total of 891 bits. By specifying a predetermined order, one can reduce this more drastically to just the 4 bits for each value for a total of 324 bits. However, a sudoku can have missing numbers. This provides the potential for reducing the number of numbers that have to be specified, but may require additional bits for indicating positions.  Using our 11-bit encoding of (position, value), we can specify a puzzle with $n$ clues with $11n$ bits, e.g. a minimal (17) puzzle requires 187 bits.  The best encoding I've thought of so far is to use one bit for each space to indicate whether it's filled and, if so, the following 4 bits encode the number. This requires $81+4n$ bits, 149 for a minimal puzzle ($n=17$). Is there a more efficient encoding, preferably without a database of each valid sudoku setup? (Bonus points for addressing a general $n$ from $N \times N$ puzzle)

It just occurred to me that many puzzles will be a rotation of another, or have a simple permutation of digits.  Perhaps that could help reduce the bits required.

According to Wikipedia,

  The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS), or approximately $6.67×10^{21}$.

If I did my math right ($\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$), that comes out to 73 (72.498) bits of information for a lookup table.

But:

  The number of essentially different solutions, when symmetries such as rotation, reflection, permutation and relabelling are taken into account, was shown to be just 5,472,730,538[15] (sequence A109741 in OEIS).

That gives 33 (32.35) bits, so it's possible that a clever method of indicating which permutation to use could get below the full 73 bits.


texts:
How could one reasonably define and construct the complement of a deterministic Mealy machine?

My intuition is that the complement should give exactly the opposite of output strings after a specific input string. I think this means the complement is non-deterministic. So let's define a (non-deterministic) Mealy machine: $\mathcal{M} = \langle S,I,\Sigma,\Omega,\delta,\lambda\rangle$, where

$S$ is a finite nonempty set of states,
$I \subseteq S$ is the nonempty set of initial states,
$\Sigma$ is a finite input alphabet,
$\Omega$ is a finite output alphabet,
$\delta: S \times \Sigma \to 2^S$ is the transition function, and
$\lambda: S \times \Sigma \to 2^\Omega$ is the output function.

A Mealy machine is deterministic iff $\vert I\vert = 1 \land \forall s \in S, \forall i \in \Sigma: \vert\delta(s, i)\vert \leq 1 \land \vert\lambda(s, i)\vert \leq 1$.

I believe defining and constructing the complement is easier if we assume the transition function, and output function are total. That is fine for me.

So, given a Mealy machine $\mathcal{M}$ how would one define, and construct (using an algorithm) the complement $\overline{\mathcal{M}}$?

If the algorithm follows trivially from the definition of $\overline{\mathcal{M}}$ that is fine too.

My first idea is that one could, for every transition, add new transitions (from, and to the same state) that give exactly the complement of outputs. However, I am afraid I am missing important corner cases.


texts:
How would you choose the second hash function with for double hashing with string as key?
My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is that a good first hash function? And what should I do for the second function now?
hanks in advance.


texts: Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account?

texts:
I've been reading a number of quantum computation research papers that claim quantum cost's that do not add up.

For instance, in this paper - there is a claim that the MTSG gate is a quantum cost of 6. But to actually perform the computation, you need swap gates to get the stuff into the right order!

For instance, to even perform the first gate V(B, D), you'll need to do the following:

1) U = TENSOR(ID, SWAP, ID)
 2) U = TENSOR(ID, ID, VGATE)
 3) APPLY (U, R)
 4) SWAP BACK

Am I getting something wrong here?


texts: Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be decidable?

texts: Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be undecidable?


texts: Dynamic Programming Subset Sum Problem with twist

texts:
Question:  You are given an input , which is a sequence of positive integers $w_1, w_2, . . . , w_n$ with parameters $W, ∆. $We wish to find
$S ⊆ \{1, 2, . . . , n\}$ such that $\sum_{j \in S} w_j$ is as large as possible, subject to the constraints that (a)$\sum_{j \in S} w_j≤ W$,
and (b) for all $i, j ∈ S$, if $i \neq j$ then $|w_i − w_j | ≥ ∆.$

Here is the recursive formula I came up with (which is incorrect).

$$OPT(i,w) =
 \begin{cases}
OPT(i-1, w) & : \text{if  } w < w_i  \\
w_1 & : \text{if   } i = 1 \text{and  } w_1 \le W\\
OPT(i, w) = max(OPT(i-2, w), OPT(i-1, w), w_i + OPT(i-2, w-w_i)) & : \text{if  } |w_i - w_{i-1} | < \Delta\\
OPT(i, w) = max(OPT(i-1, w), w_i + OPT(i-1, w-w_i)) & : otherwise
\end{cases}$$
A
The problem with the above formula is that it only checks if the $i-1^{st}$ weight is compatible with the $i^{th}$. It doesn't check if the $i^{th}$ weight is compatible with all the weights in the optimal solution. For example, if $\Delta = 2, W = 6, w_1 = 3, w_2 = 1, w_3 = 2$ then the recursive formula returns 5 instead of 3.

I would appreciate any help. Thanks.


texts: Why can't you write the 2-paths problem as a max-flow problem?

texts:
This is a follow-up question to this. Consider the 2-paths problem:

  Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and $P_2=(s_2,\dots,t_2)$ such that $P_1$ and $P_2$ are vertex-disjoint?

This problem has been shown to be NP-complete (references here).
This struck me as unusual, because there seems to be a natural way to formulate this as a max flow problem:

Add new vertices $s$ and $t$ to $D$.
Add arcs $(s,s_1),(s,s_2),(t_1,t),(t_2,t)$.
Let all vertices have capacity one (besides $s$ and $t$).

It seems to me that the max $s-t$ flow of this new graph (call it $D'$) should be two iff $D$ has those desired paths $P_1$ and $P_2$. Surely there must be some mistake here, because this seems to imply that an NP-complete problem can be solved in polytime. Where is the mistake?


texts:
I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it.
Here is an image to illustrate what I want:

The figure shows a chain consisting of 3 individual lines. The lines are always connected, but their connecting points can be moved. The goal is to fit the connecting points such that the resulting lines are in a sense optimal with respect to the points/pixels (here in black with blue border), for example minimzing some distance. It would be nice if one could adapt this optimality criterion, e.g., such that the lines might snap to the point cloud coming from below the point cloud.
In my current problem I could also give some side conditions for the connecting (yellow) points, such as: point 1 has to be somewhere between x and y on the horizontal axis. Also, I could give conditions on the angles between the lines.
It would be awesome if someone could point me in the right direction and tell me actually what I am looking for :)


texts: Reducing an FNP search problem to an NP-complete decision problem

texts:
Let us say that a search problem $R$ has an A-reduction if there is a polynomial algorithm $A$ that solves $R$ using an oracle to the decision problem $S_R$, so that for each input $x$, the number of oracle calls that $A$ makes is at most $100\log|x|$.
Assume that $\mathsf{P} \ne \mathsf{NP}$. Prove or disprove:
There is a search problem $R \in \mathsf{FNP}$ so that $S_R$ is $\mathsf{NPC}$ and $R$ has an A-reduction.

I am a bit confused about what "at most $100\log|x|$" means. I also don’t know how to find a search problem $R$ that satisfies the requirement.


texts: Equivalence of input-restricted and output-restricted deques

texts:
There is a question in Art of Computer Programming by Knuth which needs us to prove that input-restricted deques and output-restricted deques can form the same number of (and possibly individually same) permutations. The solution is

  By operating backwards, we can get the reverse of the inverse of the reverse of
  any input-restricted permutation with an output-restricted deque, and conversely. This
  rule sets up a one-to-one correspondence between the two sets of permutations.

Which doesn't seem very clear. Can someone explain the answer in English?


texts: Is knowing ALL factors of a large number an NP?

texts:
Say I have a number 45

What are the factors of 45?

1, 3, 5, 9, 15, 45

Is there any other factors?

I know that if I want to find some non trivial factor of some number, say 45, I know it's in NP.

I can non deterministically choose some 2 numbers and verify that those 2 numbers are factors of my large number. Verifying is easy. Just multiply the 2 numbers and see if it match.

What about if I want to find ALL factors of a large number? Is it still in NP?

How do we verify, in polynomial time, that 1, 3, 15, 45 are all the factors of 45? It turns out it isn't because we still have 5 and 9. But say someone says

Okay, 1, 3, 15, 45 are all factors of 45. How do we verify it in polynomial time?

Is it in NP?

Is it NP complete?

Does it has P verifier?

Basically, I wonder if the following problems are in NP

Say n is a number

Say S is a set of numbers between 1 and n

Is S the set of ALL factors of n or not.

A program should say it's false when

One element of S, say s, is not a factor of n. We can verify this by dividing n by s and see if there are some reminders.
There exist a number, say f, not in S, but is actually a factor of n.

Now is that problem NP?


texts:
I am trying to understand Y combinators. Could you please explain why the following are equivalent

(Y (f ∘ g))
(f (Y (g ∘ f)))

(Y is a fixed point combination)


texts: k-nearest neighbors (Euclidean distance): How to process multiple attributes?

texts:
Given this sample:

$$\begin{array}{|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \text{Class} \\ \hline
8 & 4 & A \\ \hline
4 & 5 & B \\ \hline
4 & 6 & B \\ \hline
7 & 7 & A \\ \hline
5 & 6 & B \\ \hline
6 & 5 & A \\ \hline
\end{array}$$
we then calculate each of Euclidean distance values to the row:

with P = (7, 4)

$$\begin{array}{|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \text{Square distance to query point  P} \\ \hline
8 & 4 & (8 - 7)^2 + (4 - 4)^2 = 1 \\ \hline
4 & 5 & (4 - 7)^2 + (5 - 4)^2 = 10 \\ \hline
4 & 6 & (4 - 7)^2 + (6 - 4)^2 = 13 \\ \hline
7 & 7 & (7 - 7)^2 + (7 - 4)^2 = 9 \\ \hline
5 & 6 & (5 - 7)^2 + (6 - 4)^2 = 8 \\ \hline
6 & 5 & (6 - 7)^2 + (5 - 4)^2 = 2 \\ \hline
\end{array}$$

But what if each class has more than one attribute , for example:
$$\begin{array}{|c|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \color{red}{X3} & \text{Square distance to query point  P} \\ \hline
8 & 4 & \color{red}{2} & (8 - 7)^2 + (4 - 4)^2 = 1 \\ \hline
4 & 5 & \color{red}{5} & (4 - 7)^2 + (5 - 4)^2 = 10 \\ \hline
4 & 6 & \color{red}{1} & (4 - 7)^2 + (6 - 4)^2 = 13 \\ \hline
7 & 7 & \color{red}{4} & (7 - 7)^2 + (7 - 4)^2 = 9 \\ \hline
5 & 6 & \color{red}{6} & (5 - 7)^2 + (6 - 4)^2 = 8 \\ \hline
6 & 5 & \color{red}{2} & (6 - 7)^2 + (5 - 4)^2 = 2 \\ \hline
\end{array}$$

How to calculate the Euclidean distance in this case?


texts: Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?

texts:
I have a graph with n edges and m vertices. This is an undirected graph.

I need to find a 3 vertex cycle. Only 3.

I'm confident I need to use an incidence matrix for this as this seems to be the best data structure. I'm familiar with cycle finding algorithms and they are all in crazy polynomial or even exponential time.

However those are for general cycles. Not 3 vertex cycles. I have O(n*m) time.

Any ideas on how to find this 3-vertex cycle in an undirected graph using an incidence matrix?

First off you can discard any row with less than 2 "1"s. Then I think I need to see some kind of a pattern in the matrix for the 3 vertex cycle. Not seeing it at the moment.

EDIT
Current idea:

Set up an array of vertices.
Go ---> in the matrix and build edges by assigning them in the matrix.
Each time edge is assigned check if that edge on both sides has a vertex with 2+ edges out.
If it has check if any of those edges out go to the same vertex [compare both lists for direct outward vertices from both sides of this edge].
If it's the same must be a 3 vertex loop.

I guess that's like rebuilding from incidence matrix to incidence list.

I'm looking at the below image from wikipedia:

https://en.wikipedia.org/wiki/Incidence_matrix


texts: Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity?

texts:
Considering the following recursive algorithm:
$ T(n)= T(\frac{n}{2})+c_1(\frac {n}{2})^2+c_2n$.
I was able to prove that this algorithm is $O(n^2 logn)$
I was trying to understand whether it is a tight bound or not, yet I was unable to prove that $ T(n)\in \Omega(n^2logn)$
Is it possible or maybe the algorithm's lower bound is $n^2$ ?
Any assistance would help a lot as I am trying to crack this for a while now.


texts:
Consider verifiers in the usual sense:

Non adaptive : reads all positions of the proof predefined

Adaptive: Reads the proof iteratively.

Many lecture notes on PCP say the following:
Adaptive verifier with q queries is equivalent to non-adaptive with some q' queries where q' is a constant and both using same randomness. In other words I think this means

Non adaptive q' queries can simulate adaptive q queries. But I don't see why? How to show this?


texts: Why does the Ford-Fulkerson Maximum flow algorithm not work for irrational capacities?

texts: Can anyone help me understand why the Ford-Fulkerson algorithm does not work in the case of irrational capacities?


texts: Radix, merge, counting sort and when to use

texts:
Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places.
So, for example,
123.456,

343.645,

234.543,

863.238,

956.043,

etc.

For which values of p should you use counting sort, radix sort, and merge sort to make it the fastest.
I know counting sort runs O(n+k), radix runs O(d(n+k)), and merge is O(n) in its best case.
Also, I *think when sorting with decimals you first multiply each by 1000 (in this case) to make them whole numbers, correct? Or is that wrong?
Any and all help would be appreciated.


texts:
I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$.

If $L \in coRP$, I don't understand how access to the oracle helps to build a probabilistic machine that proves $L \in RP^{RP}$.

Any explanation would be appreciated.


texts: Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

texts:
Is the language $ L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\} $ regular?

My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number of digits in 10-base system, but bigger or equal to $ p $, that is $ n = 10^{2m - 1} $ for appropriate $ m $.

According to the Lemma, $ z = a^n = a^{10^{2m - 1}} = uvw $, and $ |uv| \leq p $, with $ v\neq \varepsilon $. So, we pump down $ v $, and we got the $ z' $ which should be in $ L $ (by the Lemma). That is $ uw $ should be in the language. If $ |v| $ is smaller than $ 10^{2m-1} - 10^{2m-3} $, than we reach a contradiction. If $ |v| $ is bigger, than we pump it up 10 times, to reach a contradiction again. I hope this is alright.


texts: Complexity of a recursive bignum multiplication algorithm

texts:
We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little.
The exercise

Consider the problem of multiplying two big integers, i.e. integers represented by a large number of bits that cannot be handled directly by the ALU of a single CPU. This type of multiplication has applications in data security where big integers are used in encryption schemes. The elementary-school algorithm for multiplying two n-bit integers has a complexity of . To improve this complexity, let x and y be the two n-bit integers, and use the following algorithm
Recursive-Multiply(x,y)
  Write  x = x1 * 2^(n/2)+x0  //x1 and x0 are high order and low order n/2 bits
       y = y1 * 2^(n/2)+y0//y1 and y0  are high order and low order n/2 bits
  Compute x1+x0  and y1+y0
  p = Recursive-Multiply (x1+x0,y1+y0)
  x1y1 = Recursive-Multiply (x1,y1)
  x0y0 = Recursive-Multiply (x0,y0)
  Return  x1y1*2^n + (p-x1y1-x0y0)*2^(n/2)+x0y0

(a) Explain how the above algorithm works and provides the correct answer.
(b) Write a recurrence relation for the number of basic operations for the above algorithm.
(c) Solve the recurrence relation and show that its complexity is $O(n^{\lg 3})$

My conjecture

Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.

My questions

What do they mean by hi-lo order bits?

How can I use a recurrence relation on this if I don't know how each recursion works?